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/// Limits on what one lowering may do. Untrusted trees and templates cannot
37/// exceed them; exceeding one is a reported problem or error, never a hang.
38///
39/// `#[non_exhaustive]`: start from [`Budget::default`] and assign fields.
40///
41/// # Examples
42///
43/// ```
44/// use lower_lang::Budget;
45///
46/// let mut budget = Budget::default();
47/// budget.max_nodes = 1_000;
48/// assert_eq!(budget.max_expansion_depth, 64);
49/// ```
50#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
51#[non_exhaustive]
52pub struct Budget {
53    /// The most HIR nodes (and list entries) one lowering may build, copies
54    /// for repeated template holes included; past it lowering stops with
55    /// [`LowerError::NodeBudget`]. Default `1 << 24` (16,777,216).
56    pub max_nodes: u64,
57    /// The deepest chain of template applications
58    /// ([`TemplateBuilder::apply`](crate::TemplateBuilder::apply)); a deeper
59    /// one becomes an error node and an
60    /// [`ExpansionTooDeep`](ProblemKind::ExpansionTooDeep) problem.
61    /// Default 64.
62    pub max_expansion_depth: u32,
63}
64
65impl Default for Budget {
66    fn default() -> Self {
67        Self {
68            max_nodes: 1 << 24,
69            max_expansion_depth: 64,
70        }
71    }
72}
73
74/// The result of lowering: a valid HIR unit and every problem found.
75///
76/// The HIR is valid even when there are problems: each broken construct is an
77/// HIR error form, and the rest of the unit is lowered normally.
78///
79/// # Examples
80///
81/// See [`lower`](crate::lower).
82#[derive(Clone, Debug)]
83#[non_exhaustive]
84pub struct Lowered {
85    /// The validated HIR.
86    pub hir: Hir,
87    /// Every problem, in source order (span start, then discovery).
88    pub problems: Vec<Problem>,
89}
90
91impl Lowered {
92    /// Whether any problem was found.
93    ///
94    /// # Examples
95    ///
96    /// ```
97    /// use lower_lang::{lower, Arch, MappingBuilder, Pick};
98    /// use syntax_lang::Node;
99    ///
100    /// # #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
101    /// # struct K(u8);
102    /// # impl syntax_lang::TokenKind for K {}
103    /// let mut b = MappingBuilder::new();
104    /// b.node(K(0), Arch::Module { name: Pick::Absent, items: Pick::Nodes });
105    /// let mapping = b.build()?;
106    /// let tree = Node::new(K(0), vec![]);
107    /// let mut names = intern_lang::Interner::new();
108    /// let out = lower(&tree, "", &mapping, &mut names).expect("within budget");
109    /// assert!(!out.has_problems());
110    /// # Ok::<(), lower_lang::MappingError>(())
111    /// ```
112    #[must_use]
113    pub fn has_problems(&self) -> bool {
114        !self.problems.is_empty()
115    }
116}
117
118/// Lowers syntax trees with one mapping: the configured path, for a budget,
119/// a compilation unit other than 0, or host-provided field labels.
120///
121/// # Examples
122///
123/// ```
124/// use hir_lang::UnitId;
125/// use lower_lang::{Arch, Budget, Lowerer, MappingBuilder, Pick};
126/// use syntax_lang::Node;
127///
128/// # #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
129/// # struct K(u8);
130/// # impl syntax_lang::TokenKind for K {}
131/// let mut b = MappingBuilder::new();
132/// b.node(K(0), Arch::Module { name: Pick::Absent, items: Pick::Nodes });
133/// let mapping = b.build()?;
134/// let tree = Node::new(K(0), vec![]);
135/// let mut names = intern_lang::Interner::new();
136/// let out = Lowerer::new(&mapping)
137///     .with_unit(UnitId::new(3))
138///     .with_budget(Budget::default())
139///     .lower(&tree, "", &mut names)
140///     .expect("within budget");
141/// assert_eq!(out.hir.unit(), UnitId::new(3));
142/// # Ok::<(), lower_lang::MappingError>(())
143/// ```
144pub struct Lowerer<'m, K> {
145    mapping: &'m Mapping<K>,
146    budget: Budget,
147    unit: UnitId,
148    labeler: Option<&'m dyn Labeler<K>>,
149}
150
151impl<'m, K> Lowerer<'m, K>
152where
153    K: Copy + Ord + TokenKind,
154{
155    /// A lowerer for `mapping`, with the default budget, unit 0, and no field
156    /// labels.
157    ///
158    /// # Examples
159    ///
160    /// See [`Lowerer`].
161    #[must_use]
162    pub fn new(mapping: &'m Mapping<K>) -> Self {
163        Self {
164            mapping,
165            budget: Budget::default(),
166            unit: UnitId::default(),
167            labeler: None,
168        }
169    }
170
171    /// Sets the budget.
172    ///
173    /// # Examples
174    ///
175    /// See [`Lowerer`].
176    #[must_use]
177    pub fn with_budget(mut self, budget: Budget) -> Self {
178        self.budget = budget;
179        self
180    }
181
182    /// Sets the compilation unit the HIR is built for.
183    ///
184    /// # Examples
185    ///
186    /// See [`Lowerer`].
187    #[must_use]
188    pub fn with_unit(mut self, unit: UnitId) -> Self {
189        self.unit = unit;
190        self
191    }
192
193    /// Uses `labeler` for [`Pick::Label`](crate::Pick::Label) fields.
194    ///
195    /// # Examples
196    ///
197    /// ```
198    /// use lower_lang::{Labeler, Lowerer, MappingBuilder};
199    /// use syntax_lang::Node;
200    ///
201    /// struct NoFields;
202    /// # #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
203    /// # struct K(u8);
204    /// # impl syntax_lang::TokenKind for K {}
205    /// impl Labeler<K> for NoFields {
206    ///     fn label(&self, _: &Node<K>, _: usize) -> Option<u16> { None }
207    /// }
208    /// let mapping = MappingBuilder::<K>::new().build()?;
209    /// let _lowerer = Lowerer::new(&mapping).with_labeler(&NoFields);
210    /// # Ok::<(), lower_lang::MappingError>(())
211    /// ```
212    #[must_use]
213    pub fn with_labeler(mut self, labeler: &'m dyn Labeler<K>) -> Self {
214        self.labeler = Some(labeler);
215        self
216    }
217
218    /// Lowers `tree` (parsed from `source`) into a validated HIR unit, with
219    /// names interned in `names`.
220    ///
221    /// # Errors
222    ///
223    /// Only for exhausted resources: [`LowerError::NodeBudget`],
224    /// [`LowerError::SymbolSpaceExhausted`], or [`LowerError::Hir`] when
225    /// hir-lang's arenas overflow. Problems in the code are never errors:
226    /// they are in [`Lowered::problems`].
227    ///
228    /// # Examples
229    ///
230    /// See [`Lowerer`].
231    pub fn lower(
232        &self,
233        tree: &Node<K>,
234        source: &str,
235        names: &mut Interner,
236    ) -> Result<Lowered, LowerError> {
237        Run::new(self, source, names)?.run(tree)
238    }
239}
240
241// ------------------------------------------------------------------ machine
242
243/// Where a pattern's binders are bound.
244#[derive(Clone, Copy, Debug, PartialEq, Eq)]
245pub(crate) struct PatSite {
246    /// A parameter (binders of kind `Param`) rather than a local.
247    pub(crate) param: bool,
248    /// The binders are mutable.
249    pub(crate) mutable: bool,
250    /// A `match` arm, where bare identifiers follow the language's
251    /// [`IdentPatterns`](crate::IdentPatterns) policy.
252    pub(crate) arm: bool,
253    /// A range bound: bare identifiers are constants, not bindings.
254    pub(crate) bound: bool,
255}
256
257impl PatSite {
258    pub(crate) const LOCAL: Self = Self {
259        param: false,
260        mutable: false,
261        arm: false,
262        bound: false,
263    };
264    pub(crate) const ARM: Self = Self {
265        param: false,
266        mutable: false,
267        arm: true,
268        bound: false,
269    };
270}
271
272/// The context an element is lowered in, and so the kind of value it leaves.
273#[derive(Clone, Copy, Debug, PartialEq, Eq)]
274pub(crate) enum Want {
275    /// The root module.
276    Root,
277    /// An expression.
278    Expr,
279    /// An element of a block or module body: a statement, an expression, or
280    /// an item.
281    Stmt,
282    /// A member of a class, interface, or impl: an item or a field.
283    Member,
284    /// A pattern.
285    Pat(PatSite),
286    /// A type.
287    Ty,
288    /// A path in a namespace.
289    Path(Ns),
290    /// A path segment.
291    Segment,
292    /// A parameter.
293    Param,
294    /// A call argument.
295    Arg,
296    /// A match arm or catch clause.
297    Arm,
298    /// An explicit capture.
299    Capture,
300    /// A field definition.
301    Field,
302    /// A sum variant.
303    Variant,
304    /// A generic parameter.
305    Generic,
306    /// A generic argument.
307    GArg,
308    /// A where-clause predicate.
309    Where,
310    /// A map-literal entry.
311    Entry,
312    /// A record-literal field initializer.
313    Init,
314    /// A record-pattern field.
315    FieldPat(PatSite),
316}
317
318impl Want {
319    pub(crate) const fn context(self) -> Context {
320        match self {
321            Self::Root | Self::Stmt => Context::Statement,
322            Self::Expr => Context::Expression,
323            Self::Member => Context::Member,
324            Self::Pat(_) | Self::FieldPat(_) => Context::Pattern,
325            Self::Ty => Context::Type,
326            Self::Path(_) => Context::Path,
327            Self::Segment => Context::Segment,
328            Self::Param => Context::Parameter,
329            Self::Arg => Context::Argument,
330            Self::Arm => Context::Arm,
331            Self::Capture => Context::Capture,
332            Self::Field => Context::Field,
333            Self::Variant => Context::Variant,
334            Self::Generic | Self::GArg | Self::Where => Context::Generic,
335            Self::Entry | Self::Init => Context::Entry,
336        }
337    }
338
339    /// Whether an expression's value adapts to this context.
340    pub(crate) const fn takes_expr(self) -> bool {
341        matches!(
342            self,
343            Self::Expr | Self::Stmt | Self::Arg | Self::Entry | Self::GArg
344        )
345    }
346}
347
348/// The value one lowered element leaves on the value stack.
349#[derive(Clone, Copy, Debug)]
350pub(crate) enum Val {
351    /// Nothing: an absent element, or a list element that failed and was
352    /// dropped (its problem already reported).
353    Err,
354    Expr(ExprId),
355    Stmt(StmtId),
356    Item(ItemId),
357    /// Several values from one element (a `Splice`, `global $a, $b`): a run of
358    /// the spill stack. Spill entries are never themselves spills.
359    Spill(u32, u32),
360    Pat(PatId),
361    /// A `..` marker in a pattern list, with its optional binding.
362    Rest(Option<PatId>),
363    Ty(TyId),
364    Path(PathId),
365    Seg(Segment),
366    /// A parameter, created as a node by the enclosing function so that list
367    /// markers can still adjust its kind.
368    Param(Param, Span),
369    /// A `*` or `/` marker in a parameter list.
370    Marker(ParamKind),
371    Arg(Arg),
372    Arm(hir_lang::Arm),
373    Cap(Capture),
374    /// A field definition, and whether it has a name.
375    Field(hir_lang::FieldId, bool),
376    Variant(VariantId),
377    Generic(GenericParam),
378    GArg(GenericArg),
379    Where(WherePred),
380    Entry(MapEntry),
381    Init(FieldInit),
382    FieldPat(FieldPat),
383}
384
385/// A value on the value stack, with the span of the element it came from and
386/// whether it is a place (for place arguments).
387#[derive(Clone, Copy, Debug)]
388pub(crate) struct Slot {
389    pub(crate) v: Val,
390    pub(crate) span: Span,
391    pub(crate) place: bool,
392}
393
394/// A unit of work.
395#[derive(Clone, Copy)]
396pub(crate) enum Task<'t, K> {
397    /// Lower this element in this context.
398    Elem(&'t Element<K>, Want),
399    /// Lower this node in this context (the root).
400    Node(&'t Node<K>, Want),
401    /// Finish the innermost open frame.
402    Finish,
403}
404
405/// What a frame builds when it finishes.
406#[derive(Clone, Copy, Debug)]
407pub(crate) enum Build {
408    /// The frame's archetype, in its context.
409    Arch,
410    /// An operator node lowered through an operator spec.
411    Op(OpSpec),
412    /// A template instantiation.
413    Template {
414        id: TemplateId,
415        label: Option<BinderId>,
416        nodes_at: u64,
417    },
418    /// A synthetic module around a root that is not a module.
419    RootWrap,
420    /// `var x = init` hoisted: an assignment to the hoisted name.
421    HoistedLet { name: Symbol, name_span: Span },
422}
423
424/// An open construct whose fields are being lowered.
425#[derive(Clone, Copy, Debug)]
426pub(crate) struct Frame<K> {
427    pub(crate) arch: Arch<K>,
428    pub(crate) build: Build,
429    pub(crate) want: Want,
430    pub(crate) span: Span,
431    pub(crate) vals_base: usize,
432    pub(crate) counts_base: usize,
433    pub(crate) nfields: usize,
434    pub(crate) spill_base: usize,
435    pub(crate) label_mark: usize,
436    pub(crate) mods: u32,
437    pub(crate) fx: bool,
438    pub(crate) or: bool,
439    /// Names read synchronously at entry (declaration names, aliases,
440    /// members, labels).
441    pub(crate) name: Option<(Symbol, Span)>,
442    /// A binder created or found at entry (a label, a pattern's binder).
443    pub(crate) binder: Option<BinderId>,
444    /// A tuple-field index (`a.0`).
445    pub(crate) index: Option<u32>,
446    /// An archetype-specific flag: a member access is a call, a generic
447    /// parameter is a region.
448    pub(crate) flag: bool,
449    /// A path's root, read from its leading tokens.
450    pub(crate) path_root: hir_lang::PathRoot,
451}
452
453/// A function, closure, or module body under construction: its effects and
454/// its hoisted declarations.
455#[derive(Clone, Copy, Debug)]
456pub(crate) struct Fx {
457    pub(crate) declared: Effects,
458    pub(crate) inferred: Effects,
459    pub(crate) hoist_base: usize,
460    pub(crate) decl_base: usize,
461}
462
463/// One lowering run.
464pub(crate) struct Run<'a, 't, K> {
465    pub(crate) m: &'a Mapping<K>,
466    pub(crate) src: &'t str,
467    pub(crate) labeler: Option<&'a dyn Labeler<K>>,
468    pub(crate) names: &'a mut Interner,
469    pub(crate) b: Builder,
470    pub(crate) nodes: u64,
471    pub(crate) budget: Budget,
472    pub(crate) syms: Vec<Symbol>,
473    pub(crate) empty: Symbol,
474    pub(crate) sym_failed: bool,
475    pub(crate) tasks: Vec<Task<'t, K>>,
476    pub(crate) vals: Vec<Slot>,
477    pub(crate) frames: Vec<Frame<K>>,
478    pub(crate) counts: Vec<usize>,
479    pub(crate) spill: Vec<Slot>,
480    pub(crate) kids: Vec<Kid<'t, K>>,
481    pub(crate) kids2: Vec<Kid<'t, K>>,
482    pub(crate) sel: Vec<&'t Element<K>>,
483    pub(crate) labels: BTreeMap<Symbol, Vec<BinderId>>,
484    pub(crate) label_log: Vec<Symbol>,
485    pub(crate) fx: Vec<Fx>,
486    pub(crate) hoist: Vec<(Symbol, Span)>,
487    pub(crate) declared: Vec<Symbol>,
488    pub(crate) or_depth: u32,
489    pub(crate) or_map: BTreeMap<Symbol, BinderId>,
490    pub(crate) problems: Vec<Problem>,
491    pub(crate) text: Vec<u8>,
492    pub(crate) scratch: String,
493    pub(crate) bufs: Vec<Vec<Slot>>,
494    pub(crate) tpl_scratch: tpl::TplScratch,
495    pub(crate) lists: Lists,
496    pub(crate) tfields: Vec<(Pick<K>, Want, bool)>,
497}
498
499/// Typed scratch lists for building HIR lists without allocating per node.
500#[derive(Default)]
501pub(crate) struct Lists {
502    pub(crate) exprs: Vec<ExprId>,
503    pub(crate) tys: Vec<TyId>,
504    pub(crate) args: Vec<Arg>,
505    pub(crate) arms: Vec<hir_lang::Arm>,
506    pub(crate) stmts: Vec<StmtId>,
507    pub(crate) params: Vec<hir_lang::ParamId>,
508    pub(crate) gargs: Vec<GenericArg>,
509}
510
511impl<'a, 't, K> Run<'a, 't, K>
512where
513    K: Copy + Ord + TokenKind,
514{
515    fn new(
516        cfg: &Lowerer<'a, K>,
517        src: &'t str,
518        names: &'a mut Interner,
519    ) -> Result<Self, LowerError> {
520        let empty = names
521            .try_intern("")
522            .map_err(|_| LowerError::SymbolSpaceExhausted)?;
523        let mut syms = Vec::with_capacity(cfg.mapping.strings.len());
524        for s in &cfg.mapping.strings {
525            syms.push(
526                names
527                    .try_intern(s)
528                    .map_err(|_| LowerError::SymbolSpaceExhausted)?,
529            );
530        }
531        Ok(Self {
532            m: cfg.mapping,
533            src,
534            labeler: cfg.labeler,
535            names,
536            b: Builder::for_unit(cfg.unit),
537            nodes: 0,
538            budget: cfg.budget,
539            syms,
540            empty,
541            sym_failed: false,
542            tasks: Vec::new(),
543            vals: Vec::new(),
544            frames: Vec::new(),
545            counts: Vec::new(),
546            spill: Vec::new(),
547            kids: Vec::new(),
548            kids2: Vec::new(),
549            sel: Vec::new(),
550            labels: BTreeMap::new(),
551            label_log: Vec::new(),
552            fx: Vec::new(),
553            hoist: Vec::new(),
554            declared: Vec::new(),
555            or_depth: 0,
556            or_map: BTreeMap::new(),
557            problems: Vec::new(),
558            text: Vec::new(),
559            scratch: String::new(),
560            bufs: Vec::new(),
561            tpl_scratch: tpl::TplScratch::default(),
562            lists: Lists::default(),
563            tfields: Vec::new(),
564        })
565    }
566
567    fn run(mut self, tree: &'t Node<K>) -> Result<Lowered, LowerError> {
568        self.tasks.push(Task::Node(tree, Want::Root));
569        while let Some(task) = self.tasks.pop() {
570            match task {
571                Task::Elem(Element::Node(n), want) => self.lower_node(n, want),
572                Task::Elem(Element::Token(t), want) => self.lower_token(t, want),
573                Task::Node(n, want) => self.lower_node(n, want),
574                Task::Finish => self.finish(),
575            }
576            if self.nodes > self.budget.max_nodes {
577                return Err(LowerError::NodeBudget {
578                    limit: self.budget.max_nodes,
579                });
580            }
581            if self.sym_failed {
582                return Err(LowerError::SymbolSpaceExhausted);
583            }
584        }
585        let root = match self.vals.pop().map(|s| s.v) {
586            Some(Val::Item(root)) => root,
587            _ => {
588                self.b.set_origin(Origin::new(tree.span()));
589                self.b.module(None, &[])
590            }
591        };
592        let (hir, errors) = self.b.finish_lenient(root).map_err(LowerError::Hir)?;
593        let mut problems = self.problems;
594        problems.reserve(errors.len());
595        for e in errors {
596            let span = hir_span(&hir, &e);
597            problems.push(Problem {
598                kind: ProblemKind::Hir(e),
599                span,
600            });
601        }
602        problems.sort_by_key(|p| p.span.start());
603        Ok(Lowered { hir, problems })
604    }
605
606    // ------------------------------------------------------------- dispatch
607
608    fn lower_node(&mut self, node: &'t Node<K>, want: Want) {
609        let span = node.span();
610        if self.m.is_error(node.kind()) {
611            self.report(ProblemKind::SyntaxError, span);
612            let v = self.error_val(want, span);
613            self.push(v, span);
614            return;
615        }
616        pick::collect_kids(node, self.labeler, &mut self.kids);
617        let (start, end) = self.m.rule_range(node.kind());
618        let mut chosen = None;
619        for &(_, rule) in self.m.by_kind.get(start..end).unwrap_or(&[]) {
620            let Some(rule) = self.m.rules.get(rule as usize) else {
621                continue;
622            };
623            if rule.when.is_absent() || pick::single(rule.when, &self.kids, self.m).is_some() {
624                chosen = Some(rule.arch);
625                break;
626            }
627        }
628        match chosen {
629            Some(arch) => self.enter(node, arch, want),
630            None => {
631                self.report(ProblemKind::Unmapped, span);
632                let v = self.error_val(want, span);
633                self.push(v, span);
634            }
635        }
636    }
637
638    /// Leaves a value for the element at `span`.
639    pub(crate) fn push(&mut self, v: Val, span: Span) {
640        self.vals.push(Slot {
641            v,
642            span,
643            place: false,
644        });
645    }
646
647    /// Leaves a value that may be a place.
648    pub(crate) fn push_place(&mut self, v: Val, span: Span, place: bool) {
649        self.vals.push(Slot { v, span, place });
650    }
651
652    // -------------------------------------------------------------- frames
653
654    /// Opens a frame for `node` and schedules its fields: each `(pick, want,
655    /// many)` is resolved against the node's children (already in
656    /// `self.kids`), and one task per selected child is pushed.
657    pub(crate) fn plan(&mut self, mut frame: Frame<K>, fields: &[(Pick<K>, Want, bool)]) {
658        let counts_base = self.counts.len();
659        self.sel.clear();
660        for &(p, _, many) in fields {
661            let before = self.sel.len();
662            if many {
663                pick::list(p, &self.kids, self.m, &mut self.sel);
664            } else if let Some(e) = pick::single(p, &self.kids, self.m) {
665                self.sel.push(e);
666            }
667            self.counts.push(self.sel.len() - before);
668        }
669        self.drop_shared_children(fields, counts_base);
670        frame.counts_base = counts_base;
671        frame.nfields = fields.len();
672        frame.vals_base = self.vals.len();
673        frame.spill_base = self.spill.len();
674        self.frames.push(frame);
675        self.tasks.push(Task::Finish);
676        let mut end = self.sel.len();
677        for (i, &(_, want, _)) in fields.iter().enumerate().rev() {
678            let n = self.counts.get(counts_base + i).copied().unwrap_or(0);
679            let start = end.saturating_sub(n);
680            if let Some(slice) = self.sel.get(start..end) {
681                for &e in slice.iter().rev() {
682                    self.tasks.push(Task::Elem(e, want));
683                }
684            }
685            end = start;
686        }
687        self.sel.clear();
688    }
689
690    /// A child selected by an earlier field is not lowered again for a later
691    /// single-valued field: that field is left absent and the conflict is
692    /// reported. Positional picks alias this way in half-typed code (a
693    /// missing condition makes "the first node" the body).
694    fn drop_shared_children(&mut self, fields: &[(Pick<K>, Want, bool)], counts_base: usize) {
695        let mut offset = 0;
696        for (i, &(_, _, many)) in fields.iter().enumerate() {
697            let c = self.counts.get(counts_base + i).copied().unwrap_or(0);
698            if !many && c == 1 {
699                if let Some(&e) = self.sel.get(offset) {
700                    let earlier = self.sel.get(..offset).unwrap_or(&[]);
701                    if earlier.iter().any(|&x| core::ptr::eq(x, e)) {
702                        let _ = self.sel.remove(offset);
703                        if let Some(slot) = self.counts.get_mut(counts_base + i) {
704                            *slot = 0;
705                        }
706                        self.report(ProblemKind::AmbiguousChild, e.span());
707                        continue;
708                    }
709                }
710            }
711            offset += c;
712        }
713    }
714
715    /// A frame for `node` with nothing scheduled yet.
716    pub(crate) fn frame(&self, arch: Arch<K>, want: Want, span: Span) -> Frame<K> {
717        Frame {
718            arch,
719            build: Build::Arch,
720            want,
721            span,
722            vals_base: 0,
723            counts_base: 0,
724            nfields: 0,
725            spill_base: 0,
726            label_mark: self.label_log.len(),
727            mods: 0,
728            fx: false,
729            or: false,
730            name: None,
731            binder: None,
732            index: None,
733            flag: false,
734            path_root: hir_lang::PathRoot::Relative,
735        }
736    }
737
738    /// The value range of field `i` of `f`.
739    pub(crate) fn field_range(&self, f: &Frame<K>, i: usize) -> (usize, usize) {
740        let counts = self
741            .counts
742            .get(f.counts_base..f.counts_base + f.nfields)
743            .unwrap_or(&[]);
744        let start = f.vals_base + counts.iter().take(i).sum::<usize>();
745        let len = counts.get(i).copied().unwrap_or(0);
746        (start, start + len)
747    }
748
749    /// The first value of field `i` (or `Val::Err` when absent).
750    pub(crate) fn one(&self, f: &Frame<K>, i: usize) -> Val {
751        self.slot(f, i).map_or(Val::Err, |s| s.v)
752    }
753
754    /// The first slot of field `i`.
755    pub(crate) fn slot(&self, f: &Frame<K>, i: usize) -> Option<Slot> {
756        let (s, e) = self.field_range(f, i);
757        if s < e {
758            self.vals.get(s).copied()
759        } else {
760            None
761        }
762    }
763
764    /// Whether field `i` selected an element at all (even one that failed).
765    pub(crate) fn present(&self, f: &Frame<K>, i: usize) -> bool {
766        let (s, e) = self.field_range(f, i);
767        s < e
768    }
769
770    /// The values of field `i`, spills flattened, into a pooled buffer.
771    pub(crate) fn many(&mut self, f: &Frame<K>, i: usize) -> Vec<Slot> {
772        let mut out = self.bufs.pop().unwrap_or_default();
773        out.clear();
774        let (s, e) = self.field_range(f, i);
775        for j in s..e {
776            match self.vals.get(j).copied() {
777                Some(Slot {
778                    v: Val::Spill(ss, sl),
779                    ..
780                }) => {
781                    let (ss, sl) = (ss as usize, sl as usize);
782                    if let Some(run) = self.spill.get(ss..ss.saturating_add(sl)) {
783                        out.extend_from_slice(run);
784                    }
785                }
786                Some(Slot { v: Val::Err, .. }) | None => {}
787                Some(slot) => out.push(slot),
788            }
789        }
790        out
791    }
792
793    /// Returns a buffer from [`many`](Self::many) to the pool.
794    pub(crate) fn give(&mut self, mut buf: Vec<Slot>) {
795        buf.clear();
796        self.bufs.push(buf);
797    }
798
799    // ------------------------------------------------------------- problems
800
801    pub(crate) fn report(&mut self, kind: ProblemKind, span: Span) {
802        self.problems.push(Problem { kind, span });
803    }
804
805    /// Reports a missing required field and returns an error expression.
806    pub(crate) fn missing_expr(&mut self, field: &'static str, span: Span) -> ExprId {
807        self.report(ProblemKind::MissingField { field }, span);
808        self.err_expr(span)
809    }
810
811    // ------------------------------------------------------- node creation
812
813    pub(crate) fn at(&mut self, span: Span) {
814        self.b.set_origin(Origin::new(span));
815    }
816
817    pub(crate) fn ex(&mut self, e: Expr) -> ExprId {
818        self.nodes += 1;
819        self.b.expr(e)
820    }
821
822    pub(crate) fn st(&mut self, s: Stmt) -> StmtId {
823        self.nodes += 1;
824        self.b.stmt(s)
825    }
826
827    pub(crate) fn pt(&mut self, p: Pat) -> PatId {
828        self.nodes += 1;
829        self.b.pat(p)
830    }
831
832    pub(crate) fn ty(&mut self, t: Ty) -> TyId {
833        self.nodes += 1;
834        self.b.ty(t)
835    }
836
837    pub(crate) fn it(&mut self, i: Item) -> ItemId {
838        self.nodes += 1;
839        self.b.item(i)
840    }
841
842    pub(crate) fn path(&mut self, p: Path) -> PathId {
843        self.nodes += 1;
844        self.b.path(p)
845    }
846
847    pub(crate) fn binder(&mut self, name: Name, kind: BinderKind, mutable: bool) -> BinderId {
848        self.nodes += 1;
849        self.b
850            .binder(hir_lang::Binder::new(name, kind).with_mutable(mutable))
851    }
852
853    pub(crate) fn list<T: hir_lang::Pooled>(&mut self, items: &[T]) -> List<T> {
854        self.nodes += items.len() as u64;
855        self.b.list(items)
856    }
857
858    pub(crate) fn err_expr(&mut self, span: Span) -> ExprId {
859        self.at(span);
860        self.ex(Expr::Err)
861    }
862
863    /// A one-segment unresolved path to a source name.
864    pub(crate) fn name_path(&mut self, sym: Symbol, span: Span, ns: Ns) -> PathId {
865        self.at(span);
866        let seg = Segment::new(Name::new(sym), Origin::new(span));
867        let segs = self.list(&[seg]);
868        self.path(Path::new(segs, ns))
869    }
870
871    pub(crate) fn name_expr(&mut self, sym: Symbol, span: Span) -> ExprId {
872        let p = self.name_path(sym, span, Ns::Value);
873        self.ex(Expr::Path(p))
874    }
875
876    /// The error value for a context: an error node where the context keeps
877    /// positions (expressions, statements, patterns, parameters, arguments),
878    /// nothing where a list can simply lose the element.
879    pub(crate) fn error_val(&mut self, want: Want, span: Span) -> Val {
880        self.at(span);
881        match want {
882            Want::Root => {
883                // The root must stay a module for hir-lang to accept the unit.
884                self.nodes += 1;
885                Val::Item(self.b.module(None, &[]))
886            }
887            Want::Member => Val::Item(self.it(Item::new(None, ItemKind::Err))),
888            Want::Expr => Val::Expr(self.ex(Expr::Err)),
889            Want::Stmt => Val::Stmt(self.st(Stmt::Err)),
890            Want::Pat(_) => Val::Pat(self.pt(Pat::Err)),
891            Want::Ty => Val::Ty(self.ty(Ty::Err)),
892            Want::Path(_) => {
893                let mut p = Path::new(List::EMPTY, Ns::Value);
894                p.res = Res::Err;
895                Val::Path(self.path(p))
896            }
897            Want::Param => {
898                let pat = self.pt(Pat::Err);
899                Val::Param(Param::new(pat), span)
900            }
901            Want::Arg => {
902                let e = self.ex(Expr::Err);
903                Val::Arg(Arg::positional(e))
904            }
905            Want::Entry => {
906                let e = self.ex(Expr::Err);
907                Val::Entry(MapEntry {
908                    key: None,
909                    value: e,
910                })
911            }
912            Want::GArg => {
913                let t = self.ty(Ty::Err);
914                Val::GArg(GenericArg::Ty(t))
915            }
916            Want::Segment
917            | Want::Arm
918            | Want::Capture
919            | Want::Field
920            | Want::Variant
921            | Want::Generic
922            | Want::Where
923            | Want::Init
924            | Want::FieldPat(_) => Val::Err,
925        }
926    }
927
928    /// Reports that a construct cannot appear in `want` and leaves its error
929    /// value.
930    pub(crate) fn not_here(&mut self, want: Want, span: Span) {
931        self.report(
932            ProblemKind::NotAllowedHere {
933                expected: want.context(),
934            },
935            span,
936        );
937        let v = self.error_val(want, span);
938        self.push(v, span);
939    }
940
941    /// Converts an expression to the value a context takes.
942    pub(crate) fn adapt_expr(&mut self, e: ExprId, place: bool, want: Want, span: Span) -> Val {
943        match want {
944            Want::Expr | Want::Stmt => Val::Expr(e),
945            Want::Arg => Val::Arg(Arg {
946                kind: ArgKind::Positional,
947                value: e,
948                place: place && self.m.policy.place_args == crate::PlaceArgs::Places,
949            }),
950            Want::Entry => Val::Entry(MapEntry {
951                key: None,
952                value: e,
953            }),
954            Want::GArg => Val::GArg(GenericArg::Const(e)),
955            _ => {
956                // Unreachable by construction (`enter` checks the context
957                // first); keep the expression attached by wrapping it in an
958                // error-free statement where possible.
959                self.report(
960                    ProblemKind::NotAllowedHere {
961                        expected: want.context(),
962                    },
963                    span,
964                );
965                self.error_val(want, span)
966            }
967        }
968    }
969
970    // ---------------------------------------------------------------- text
971
972    /// The source text of `span`, or `""` (and a problem) when the span lies
973    /// outside the source.
974    pub(crate) fn text_of(&mut self, span: Span) -> &'t str {
975        let (s, e) = (span.start().to_usize(), span.end().to_usize());
976        match self.src.get(s..e) {
977            Some(t) => t,
978            None => {
979                self.report(ProblemKind::BadSpan, span);
980                ""
981            }
982        }
983    }
984
985    pub(crate) fn intern(&mut self, s: &str) -> Symbol {
986        match self.names.try_intern(s) {
987            Ok(sym) => sym,
988            Err(_) => {
989                self.sym_failed = true;
990                self.empty
991            }
992        }
993    }
994
995    /// The mapping string `i` (texts of templates, extern names) as a symbol.
996    pub(crate) fn sym(&self, i: u32) -> Symbol {
997        self.syms.get(i as usize).copied().unwrap_or(self.empty)
998    }
999
1000    /// The name an element spells: a name-like token (sigil stripped), or a
1001    /// `Pass` wrapper around one. Other tokens count by their text.
1002    pub(crate) fn name_of(&mut self, elem: &'t Element<K>) -> Option<(Symbol, Span)> {
1003        let mut cur = elem;
1004        loop {
1005            match cur {
1006                Element::Token(t) => {
1007                    let span = t.span();
1008                    let strip = match self.m.role_for(t.kind()) {
1009                        Some(TokenRole::Name) | None => 0,
1010                        Some(
1011                            TokenRole::Var { sigil }
1012                            | TokenRole::Label { sigil }
1013                            | TokenRole::Lifetime { sigil },
1014                        ) => usize::from(sigil),
1015                        Some(_) => return None,
1016                    };
1017                    let text = self.text_of(span);
1018                    let name = text.get(strip..).unwrap_or("");
1019                    return Some((self.intern(name), span));
1020                }
1021                Element::Node(n) => {
1022                    pick::collect_kids(n, self.labeler, &mut self.kids2);
1023                    let arch = self.m.rule_for(n.kind()).copied();
1024                    let inner = match arch {
1025                        Some(Arch::Pass { inner } | Arch::Segment { name: inner, .. }) => {
1026                            pick::single(inner, &self.kids2, self.m)
1027                        }
1028                        Some(Arch::Path { segments, .. }) => {
1029                            let mut out = Vec::new();
1030                            pick::list(segments, &self.kids2, self.m, &mut out);
1031                            if out.len() == 1 {
1032                                out.first().copied()
1033                            } else {
1034                                None
1035                            }
1036                        }
1037                        _ => None,
1038                    };
1039                    cur = inner?;
1040                }
1041            }
1042        }
1043    }
1044
1045    /// The modifiers among the node's direct significant children (and the
1046    /// tokens directly inside container children).
1047    pub(crate) fn mods(&self) -> u32 {
1048        if self.m.modifiers.is_empty() {
1049            return 0;
1050        }
1051        let mut bits = 0;
1052        for kid in &self.kids {
1053            match kid.elem {
1054                Element::Token(t) => bits |= crate::mapping::modifier_bits(self.m, t.kind()),
1055                Element::Node(n) => {
1056                    if crate::pick::KindSets::is_container(self.m, n.kind()) {
1057                        for c in n.child_tokens() {
1058                            bits |= crate::mapping::modifier_bits(self.m, c.kind());
1059                        }
1060                    }
1061                }
1062            }
1063        }
1064        bits
1065    }
1066
1067    // --------------------------------------------------------------- scopes
1068
1069    pub(crate) fn push_label(&mut self, sym: Symbol, b: BinderId) {
1070        self.labels.entry(sym).or_default().push(b);
1071        self.label_log.push(sym);
1072    }
1073
1074    pub(crate) fn pop_labels(&mut self, mark: usize) {
1075        while self.label_log.len() > mark {
1076            if let Some(sym) = self.label_log.pop() {
1077                if let Some(stack) = self.labels.get_mut(&sym) {
1078                    let _ = stack.pop();
1079                }
1080            }
1081        }
1082    }
1083
1084    pub(crate) fn find_label(&self, sym: Symbol) -> Option<BinderId> {
1085        self.labels.get(&sym).and_then(|s| s.last().copied())
1086    }
1087
1088    pub(crate) fn push_fx(&mut self, declared: Effects) {
1089        self.fx.push(Fx {
1090            declared,
1091            inferred: Effects::NONE,
1092            hoist_base: self.hoist.len(),
1093            decl_base: self.declared.len(),
1094        });
1095    }
1096
1097    /// Marks the innermost function-like frame as doing `effect`.
1098    pub(crate) fn infer(&mut self, effect: Effects) {
1099        if let Some(top) = self.fx.last_mut() {
1100            top.inferred = top.inferred.union(effect);
1101        }
1102    }
1103
1104    pub(crate) fn hoist_name(&mut self, sym: Symbol, span: Span) {
1105        if !self.fx.is_empty() {
1106            self.hoist.push((sym, span));
1107        }
1108    }
1109
1110    pub(crate) fn declare_name(&mut self, sym: Symbol) {
1111        if !self.fx.is_empty() {
1112            self.declared.push(sym);
1113        }
1114    }
1115
1116    /// Closes the innermost function-like frame: its effects, and the `let`
1117    /// statements for its hoisted names (deduplicated, minus the names a
1118    /// parameter, `global`, or `static` declares), in first-use order.
1119    pub(crate) fn pop_fx(&mut self, span: Span) -> (Effects, Vec<StmtId>) {
1120        let Some(fx) = self.fx.pop() else {
1121            return (Effects::NONE, Vec::new());
1122        };
1123        let policy = self.m.policy;
1124        let mut effects = fx.declared;
1125        for (mode, flag) in [
1126            (policy.throws, Effects::THROWS),
1127            (policy.yields, Effects::YIELD),
1128            (policy.asyncs, Effects::ASYNC),
1129        ] {
1130            let add = match mode {
1131                EffectMode::Declared => false,
1132                EffectMode::Inferred => fx.inferred.contains(flag),
1133                EffectMode::Always => true,
1134            };
1135            if add {
1136                effects = effects.union(flag);
1137            }
1138        }
1139        let mut stmts = Vec::new();
1140        if self.hoist.len() > fx.hoist_base {
1141            let mut names: Vec<(Symbol, Span)> = self.hoist.split_off(fx.hoist_base);
1142            let mut declared: Vec<Symbol> = self.declared.split_off(fx.decl_base);
1143            declared.sort();
1144            names.sort_by(|a, b| a.0.cmp(&b.0).then(a.1.start().cmp(&b.1.start())));
1145            names.dedup_by(|later, first| later.0 == first.0);
1146            names.retain(|(s, _)| declared.binary_search(s).is_err());
1147            names.sort_by_key(|(_, sp)| sp.start());
1148            for (sym, sp) in names {
1149                self.at(sp);
1150                let b = self.binder(Name::new(sym), BinderKind::Local, true);
1151                let pat = self.pt(Pat::Bind {
1152                    binder: b,
1153                    mode: hir_lang::BindMode::Value,
1154                    sub: None,
1155                });
1156                stmts.push(self.st(Stmt::Let {
1157                    pat,
1158                    ty: None,
1159                    init: None,
1160                    else_: None,
1161                }));
1162            }
1163            self.at(span);
1164        } else {
1165            self.hoist.truncate(fx.hoist_base);
1166            self.declared.truncate(fx.decl_base);
1167        }
1168        (effects, stmts)
1169    }
1170
1171    /// `body`, or `{ hoisted lets; body }` when there are hoisted names.
1172    pub(crate) fn wrap_hoisted(&mut self, hoisted: &[StmtId], body: ExprId, span: Span) -> ExprId {
1173        if hoisted.is_empty() {
1174            return body;
1175        }
1176        self.at(span);
1177        let stmts = self.list(hoisted);
1178        self.ex(Expr::Block(hir_lang::Block {
1179            stmts,
1180            tail: Some(body),
1181            label: None,
1182            is_unsafe: false,
1183        }))
1184    }
1185}
1186
1187/// The span a HIR validation problem is about: its node's origin, or its
1188/// binder's or expansion's.
1189fn hir_span(hir: &Hir, e: &HirError) -> Span {
1190    match e.node() {
1191        Some(n) => hir.origin(n).span,
1192        None => match e {
1193            HirError::BinderBoundTwice { binder, .. }
1194            | HirError::BinderKind { binder, .. }
1195            | HirError::DuplicateBinding { binder, .. } => hir.binder_origin(*binder).span,
1196            HirError::Dangling {
1197                site: Site::Binder(b),
1198                ..
1199            } => hir.binder_origin(*b).span,
1200            HirError::Dangling {
1201                site: Site::Expansion(x),
1202                ..
1203            }
1204            | HirError::ExpansionOrder { expn: x } => {
1205                hir.expansion(*x).map_or(Span::empty(0), |x| x.call_site)
1206            }
1207            _ => hir.origin(NodeRef::Item(hir.root())).span,
1208        },
1209    }
1210}