Skip to main content

lower_lang/
mapping.rs

1//! The mapping: a language's semantics as data.
2//!
3//! A [`Mapping`] mirrors LexerSketch's LSF2 `[semantics]` sections:
4//! node kinds to [`Arch`]etypes (`[semantics.bind]`), templates
5//! (`[semantics.lower]`), and operators with their policies
6//! (`[semantics.ops]`), plus the token roles, modifiers, and path roots that
7//! the archetypes read. Build one with a [`MappingBuilder`]; it is immutable,
8//! `Send` and `Sync` when `K` is, and lowers any number of trees.
9
10use alloc::boxed::Box;
11use alloc::collections::BTreeMap;
12use alloc::vec::Vec;
13use core::fmt;
14
15use hir_lang::{DivZero, FloatToInt, Op, OpKind, Overflow, PathRoot, Prim, Shift, Vis};
16
17use crate::arch::{Arch, TemplateUse};
18use crate::pick::{KindSets, Pick};
19use crate::template::{HoleKind, NONE, TArg, TNode, Template, TemplateError, TemplateId};
20use crate::text::{self, Registry, SyntaxError};
21
22/// What a token means when it is lowered on its own.
23///
24/// # Examples
25///
26/// ```
27/// use lower_lang::{Escapes, TokenRole};
28///
29/// let var = TokenRole::Var { sigil: 1 };       // `$name`, name `name`
30/// let string = TokenRole::Str(Escapes::Standard);
31/// assert_ne!(var, string);
32/// ```
33#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
34#[non_exhaustive]
35pub enum TokenRole {
36    /// An identifier: a name, a variable reference, a binding, or a type name.
37    Name,
38    /// A sigiled variable such as `$x`; the first `sigil` bytes are not part
39    /// of the name.
40    Var {
41        /// Bytes to strip.
42        sigil: u8,
43    },
44    /// A loop label such as `'outer`.
45    Label {
46        /// Bytes to strip.
47        sigil: u8,
48    },
49    /// A region (lifetime) such as `'a`, as a generic parameter or argument.
50    Lifetime {
51        /// Bytes to strip.
52        sigil: u8,
53    },
54    /// An integer literal (`0x`, `0o`, `0b` prefixes and `_` separators
55    /// accepted; a registered suffix sets its type).
56    Int,
57    /// A floating-point literal.
58    Float,
59    /// A number: a float if it has a fraction or an exponent, else an integer.
60    Number,
61    /// A string literal, quotes included in the token.
62    Str(Escapes),
63    /// A raw string literal, taken verbatim: optional ASCII prefix letters
64    /// (`r`, `R`, `br`), optional `#` fences, then one quote character (`"`,
65    /// `'`, or `` ` ``), or a tripled one (`"""`, Python), closed by the same
66    /// quote(s) and the same number of `#`s. Rust `r#"a "b""#`, Python
67    /// `r'\d+'`. Malformed fences are an
68    /// [`InvalidLiteral`](crate::ProblemKind::InvalidLiteral).
69    RawStr,
70    /// A PHP heredoc (`Standard` escapes) or nowdoc (`None`) as one token:
71    /// `<<<ID` (or `<<<"ID"`, `<<<'ID'`), a newline, the body lines, and the
72    /// closing identifier on its own line. Per PHP 7.3+, the whitespace before
73    /// the closing identifier is removed from every body line (a line
74    /// indented less, or tabs mixed with spaces, is an
75    /// [`InvalidLiteral`](crate::ProblemKind::InvalidLiteral)), and the newline
76    /// before the closing identifier is not part of the string. A heredoc
77    /// with interpolation is an [`Interp`](crate::Arch::Interp) node instead.
78    Heredoc(Escapes),
79    /// A literal piece of an [interpolated string](crate::Arch::Interp): the
80    /// text between embedded expressions, without quotes; escapes decoded.
81    StrPart(Escapes),
82    /// A character literal, quotes included.
83    Char(Escapes),
84    /// A byte-string literal, quotes (and a leading `b`) included.
85    Bytes(Escapes),
86    /// `true`.
87    True,
88    /// `false`.
89    False,
90    /// `null` / `nil` / `None`-as-keyword.
91    Null,
92    /// `_`: a wildcard pattern, or an inferred type.
93    Wild,
94    /// `..` inside a pattern.
95    Rest,
96    /// A type keyword (`int`, `mixed`, `Self`, `!`).
97    Type(TypeName),
98}
99
100/// How a string or character literal's escapes are decoded.
101///
102/// # Examples
103///
104/// ```
105/// use lower_lang::Escapes;
106///
107/// assert_ne!(Escapes::None, Escapes::Standard);
108/// ```
109#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
110pub enum Escapes {
111    /// Raw: the text between the quotes, unchanged.
112    None,
113    /// Only `\\` and an escaped quote (PHP single-quoted strings).
114    Quotes,
115    /// `\n \r \t \0 \\ \' \" \$ \xHH \u{H..}`; any other escape is reported
116    /// and kept as written.
117    Standard,
118}
119
120/// A type keyword's meaning.
121///
122/// # Examples
123///
124/// ```
125/// use hir_lang::Prim;
126/// use lower_lang::TypeName;
127///
128/// assert_eq!(TypeName::Prim(Prim::I64), TypeName::Prim(Prim::I64));
129/// ```
130#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
131pub enum TypeName {
132    /// A primitive type.
133    Prim(Prim),
134    /// The gradual dynamic type (`mixed`, `any`).
135    Any,
136    /// The type of expressions that never complete (`never`, `!`).
137    Never,
138    /// `Self`.
139    SelfTy,
140    /// A type to infer (`_`, `auto`).
141    Infer,
142}
143
144/// A keyword or symbol that sets a flag on the construct it appears in.
145///
146/// Modifiers are read from the **direct** significant children of the
147/// archetypes that consult them (listed on each [`Arch`] variant), so a token
148/// can be a modifier in one construct and something else elsewhere.
149///
150/// # Examples
151///
152/// ```
153/// use lower_lang::Modifier;
154///
155/// assert_ne!(Modifier::Public, Modifier::Mut);
156/// ```
157#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
158#[non_exhaustive]
159pub enum Modifier {
160    /// `pub`, `public`.
161    Public,
162    /// `protected`.
163    Protected,
164    /// `private`.
165    Private,
166    /// `pub(crate)`, `internal`.
167    Package,
168    /// `mut`, `var`.
169    Mut,
170    /// `&` / `ref`: by reference (parameters, captures, bindings, arguments).
171    Ref,
172    /// `...` / `*` on a parameter: variadic.
173    Rest,
174    /// `**` on a parameter: collects named arguments.
175    RestNamed,
176    /// A `*` marker in a parameter list: the parameters after it are named-only.
177    NamedOnly,
178    /// A `/` marker in a parameter list: the parameters before it are
179    /// positional-only.
180    PositionalOnly,
181    /// `self` as a parameter: the method receiver.
182    Receiver,
183    /// `async`.
184    Async,
185    /// `*` on a function (`function*`), `gen`: a generator.
186    Generator,
187    /// `throws`.
188    Throws,
189    /// `unsafe`.
190    Unsafe,
191    /// `static` on a class member.
192    Static,
193    /// `abstract`.
194    Abstract,
195    /// `final`.
196    Final,
197    /// `*` in an import: a glob.
198    Glob,
199    /// `..=`: an inclusive range pattern.
200    Inclusive,
201    /// `...` on an argument: spread positional arguments.
202    Spread,
203    /// `**` on an argument: spread named arguments.
204    SpreadNamed,
205    /// `union` on a record.
206    Union,
207}
208
209impl Modifier {
210    pub(crate) const fn bit(self) -> u32 {
211        1 << (self as u32)
212    }
213}
214
215/// How a function's effects are decided.
216///
217/// # Examples
218///
219/// ```
220/// use lower_lang::EffectMode;
221///
222/// assert_eq!(EffectMode::default(), EffectMode::Declared);
223/// ```
224#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
225pub enum EffectMode {
226    /// Only what modifiers declare (`async`, `throws`, generator markers).
227    #[default]
228    Declared,
229    /// Declared, plus whatever the body does directly (a `yield` makes a
230    /// generator, as in PHP and Python; a `throw` makes it throwing).
231    Inferred,
232    /// Every function, closure, and module body has the effect (any PHP
233    /// function may throw).
234    Always,
235}
236
237/// How a bare identifier in a `match` arm pattern is lowered.
238///
239/// # Examples
240///
241/// ```
242/// use lower_lang::IdentPatterns;
243///
244/// assert_eq!(IdentPatterns::default(), IdentPatterns::Ident);
245/// ```
246#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
247pub enum IdentPatterns {
248    /// `Pat::Ident`: the resolver decides between a constant or unit variant
249    /// and a new binding (Rust, Kraken).
250    #[default]
251    Ident,
252    /// Always a new binding.
253    Bind,
254}
255
256/// Which call arguments are passed as places, so a by-reference parameter can
257/// alias them.
258///
259/// # Examples
260///
261/// ```
262/// use lower_lang::PlaceArgs;
263///
264/// assert_eq!(PlaceArgs::default(), PlaceArgs::Marked);
265/// ```
266#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
267pub enum PlaceArgs {
268    /// Only arguments with a `Ref` modifier (`f(&$x)` in old PHP, `ref x` in
269    /// C#).
270    #[default]
271    Marked,
272    /// Every argument that is a place (a variable, field, index, ...); the
273    /// callee decides at run time whether to alias it (PHP and Mox, where
274    /// by-reference is declared on the parameter).
275    Places,
276}
277
278/// What the label of a `break` or `continue` is
279/// ([`LangPolicy::break_levels`]; LSF2 `break_levels`).
280///
281/// # Examples
282///
283/// ```
284/// use lower_lang::BreakLevels;
285///
286/// assert_eq!(BreakLevels::default(), BreakLevels::Labels);
287/// ```
288#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
289#[non_exhaustive]
290pub enum BreakLevels {
291    /// A name: `break 'outer` targets the loop or block labelled `'outer`
292    /// (Rust, Kraken, JavaScript).
293    #[default]
294    Labels,
295    /// A count: `break 2` / `continue 2` target the second enclosing loop of
296    /// the same function (PHP). The level is an integer literal from 1 up
297    /// to the number of loops around the jump; `0`, anything that is not an
298    /// integer literal, or a level beyond the enclosing loops is a
299    /// [`BreakLevel`](crate::ProblemKind::BreakLevel) problem. Lowered to a
300    /// labelled HIR `break`/`continue`: the targeted loop gets a hygienic
301    /// label (or keeps its own). An [`Arch::Loop`](crate::Arch::Loop) and a
302    /// template node whose template has a label hole (`while`, `do_while`,
303    /// `c_for`, `for_each`) each count as one loop; closures and functions
304    /// start a new count.
305    Numeric,
306}
307
308/// Where `_` may separate the digits of a number.
309///
310/// # Examples
311///
312/// ```
313/// use lower_lang::Separators;
314///
315/// assert_eq!(Separators::default(), Separators::Anywhere);
316/// ```
317#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
318pub enum Separators {
319    /// After the first digit, anywhere and repeated (`1_000`, `1__0`, `10_`;
320    /// Rust, Kraken).
321    #[default]
322    Anywhere,
323    /// Only between two digits of the number's radix: `1_000` and `0xFF_FF`,
324    /// but not `1__0`, `10_`, `0x_FF`, or `1_.5` (PHP 7.4+, JavaScript; Python
325    /// also accepts `0x_FF`, which this rejects).
326    BetweenDigits,
327    /// Never (C, PHP before 7.4).
328    None,
329}
330
331/// What a leading `0` followed by more digits means (`0777`).
332///
333/// # Examples
334///
335/// ```
336/// use lower_lang::LegacyOctal;
337///
338/// assert_eq!(LegacyOctal::default(), LegacyOctal::Decimal);
339/// ```
340#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
341pub enum LegacyOctal {
342    /// Decimal: `0777` is 777 (Rust, Kraken).
343    #[default]
344    Decimal,
345    /// Octal: `0777` is 511, and `08` is invalid (C, PHP, JavaScript sloppy
346    /// mode).
347    Octal,
348    /// An error (Python 3: write `0o777`); `0`, `00`, and `0.5` stay valid.
349    Error,
350}
351
352/// How number literals are spelled and decoded: the literal decoding table.
353///
354/// Raw strings, heredocs, nowdocs, and interpolation pieces are token roles
355/// ([`TokenRole::RawStr`], [`TokenRole::Heredoc`], [`TokenRole::StrPart`]); an
356/// integer too large for 64 bits follows [`LangPolicy::overflow`] (see
357/// [`LangPolicy`]).
358///
359/// `#[non_exhaustive]`: start from [`Literals::default`] and assign fields.
360///
361/// # Examples
362///
363/// ```
364/// use lower_lang::{LegacyOctal, Literals, Separators};
365///
366/// let mut php = Literals::default();
367/// php.separators = Separators::BetweenDigits;
368/// php.legacy_octal = LegacyOctal::Octal;
369/// php.hex_floats = false;
370/// assert!(Literals::default().hex_floats);
371/// ```
372#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
373#[non_exhaustive]
374pub struct Literals {
375    /// Digit separators.
376    pub separators: Separators,
377    /// A leading zero.
378    pub legacy_octal: LegacyOctal,
379    /// Whether hexadecimal floating-point literals (`0x1.8p3` = 12.0, `0x1p-2`
380    /// = 0.25) are accepted (C, Java, Rust's `hexf`); they are decoded with
381    /// correct rounding to the nearest `f64`, subnormals included.
382    pub hex_floats: bool,
383}
384
385impl Default for Literals {
386    fn default() -> Self {
387        Self {
388            separators: Separators::Anywhere,
389            legacy_octal: LegacyOctal::Decimal,
390            hex_floats: true,
391        }
392    }
393}
394
395/// Language-wide lowering policies.
396///
397/// `#[non_exhaustive]`: start from [`LangPolicy::default`] (or
398/// [`LangPolicy::php`]) and assign fields.
399///
400/// An unsuffixed integer literal follows the overflow policy: with
401/// [`Overflow::Promote`] (PHP, whose integers are 64-bit signed) a value
402/// above `i64::MAX` is the `f64` nearest to it (`9223372036854775808` and
403/// `0xFFFF_FFFF_FFFF_FFFF` are floats, as in PHP); otherwise a decimal value
404/// beyond `u64` is an exact big integer, and a non-decimal one is converted
405/// to its exact decimal digits (up to 1,024 digits; longer is an
406/// [`InvalidLiteral`](crate::ProblemKind::InvalidLiteral)).
407///
408/// # Examples
409///
410/// ```
411/// use hir_lang::Overflow;
412/// use lower_lang::{EffectMode, LangPolicy, PlaceArgs};
413///
414/// // Mox: PHP-like integers, any function may throw, implicit locals.
415/// let mut mox = LangPolicy::default();
416/// mox.overflow = Overflow::Promote;
417/// mox.throws = EffectMode::Always;
418/// mox.yields = EffectMode::Inferred;
419/// mox.implicit_locals = true;
420/// mox.place_args = PlaceArgs::Places;
421/// assert!(mox.implicit_locals);
422/// ```
423#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
424#[non_exhaustive]
425pub struct LangPolicy {
426    /// The overflow policy of every op that consults one (OPS §2).
427    pub overflow: Overflow,
428    /// The division-by-zero policy.
429    pub div_zero: DivZero,
430    /// The shift-amount policy (`Shift::Saturate` is PHP's rule: an amount
431    /// at or above the width gives `0`, or `-1` for `shr` of a negative).
432    pub shift: Shift,
433    /// The float-to-integer conversion policy.
434    pub float_to_int: FloatToInt,
435    /// When functions, closures, and module bodies throw.
436    pub throws: EffectMode,
437    /// When they are generators.
438    pub yields: EffectMode,
439    /// When they are async.
440    pub asyncs: EffectMode,
441    /// PHP-style implicit declaration: assigning to a plain variable declares
442    /// it for the whole enclosing function (or module body) unless a
443    /// parameter, `global`, or `static` already does.
444    pub implicit_locals: bool,
445    /// Bare identifiers in `match` arm patterns.
446    pub ident_patterns: IdentPatterns,
447    /// Which arguments are passed as places.
448    pub place_args: PlaceArgs,
449    /// PHP scoping: the variables a `for-each` binds (every template pattern
450    /// hole) and the variable a `catch` binds belong to the enclosing
451    /// function (or module body), so they keep their last value after the
452    /// loop or handler. Each such pattern binds hygienic temporaries, which
453    /// are assigned to the function-scoped names right after the pattern
454    /// matches. A binding that cannot be hoisted this way (a by-reference
455    /// binding, a hole the template uses twice) is reported
456    /// ([`CannotHoist`](crate::ProblemKind::CannotHoist)) and stays scoped.
457    pub function_scoped_bindings: bool,
458    /// How number literals are spelled.
459    pub literals: Literals,
460    /// The implicit receiver (LSF2 `implicit_receiver`; PHP's `$this`): a
461    /// name stored with [`MappingBuilder::name`]. When set, every method of
462    /// a class, mixin, or interface that is not `static` (no
463    /// [`Modifier::Static`]) and has no explicit receiver parameter gets a
464    /// first parameter of kind `Receiver` binding this name, visible to the
465    /// method's body (and to its parameter defaults) as an ordinary user
466    /// name; template binders carry their expansion's mark and never
467    /// capture it. A closure inside such a method captures it as PHP does:
468    /// one that only sees explicit captures (`implicit: None`, PHP's
469    /// `function () use (...)`) gets an extra by-value capture of the
470    /// receiver; one with implicit captures reaches it through them. A
471    /// `static` closure has no receiver, and neither does any closure nested
472    /// in one: reading the name there is a
473    /// [`NoReceiver`](crate::ProblemKind::NoReceiver) problem. Functions
474    /// that are not methods (and `impl` members, which spell their
475    /// receiver) are unchanged. A name [`build`](MappingBuilder::build)
476    /// cannot find is [`MappingError::UnknownName`].
477    pub implicit_receiver: Option<NameRef>,
478    /// What a `break`/`continue` label is: a name, or (PHP) a loop count.
479    pub break_levels: BreakLevels,
480    /// The visibility of a member of a class, mixin, or interface (a
481    /// method, a property, a static, a constant) that has no visibility
482    /// modifier (LSF2 `default_visibility`). `Private` by default, as in
483    /// 0.4.0; PHP and Mox members are `Public`. Declarations outside class
484    /// bodies, `impl` members, and members with a visibility keyword are
485    /// unchanged.
486    pub default_member_visibility: Vis,
487}
488
489impl LangPolicy {
490    /// PHP and Mox: integers promote to float on overflow (OPS §2), any
491    /// function may throw, a `yield` makes a generator, assignment declares
492    /// variables for the whole function, every place argument is passed as a
493    /// place, `foreach` and `catch` variables are function-scoped, and
494    /// numbers use PHP's spelling (`_` between digits, `0777` octal, no hex
495    /// floats).
496    ///
497    /// The preset is the 0.4.0 one: it leaves
498    /// [`implicit_receiver`](Self::implicit_receiver) unset (the name comes
499    /// from a [`MappingBuilder`]), [`break_levels`](Self::break_levels) at
500    /// `Labels`, and
501    /// [`default_member_visibility`](Self::default_member_visibility) at
502    /// `Private`. PHP and Mox set all three:
503    ///
504    /// ```
505    /// use hir_lang::Vis;
506    /// use lower_lang::{BreakLevels, LangPolicy, MappingBuilder};
507    ///
508    /// let mut b = MappingBuilder::<u8>::new();
509    /// let mut mox = LangPolicy::php();
510    /// mox.implicit_receiver = Some(b.name("this"));
511    /// mox.break_levels = BreakLevels::Numeric;
512    /// mox.default_member_visibility = Vis::Public;
513    /// b.policy(mox);
514    /// assert!(b.build().is_ok());
515    /// ```
516    ///
517    /// # Examples
518    ///
519    /// ```
520    /// use hir_lang::Overflow;
521    /// use lower_lang::{LangPolicy, LegacyOctal, PlaceArgs};
522    ///
523    /// let php = LangPolicy::php();
524    /// assert_eq!(php.overflow, Overflow::Promote);
525    /// assert!(php.implicit_locals && php.function_scoped_bindings);
526    /// assert_eq!(php.place_args, PlaceArgs::Places);
527    /// assert_eq!(php.literals.legacy_octal, LegacyOctal::Octal);
528    /// assert!(!LangPolicy::default().function_scoped_bindings);
529    /// ```
530    #[must_use]
531    pub fn php() -> Self {
532        Self {
533            overflow: Overflow::Promote,
534            throws: EffectMode::Always,
535            yields: EffectMode::Inferred,
536            implicit_locals: true,
537            place_args: PlaceArgs::Places,
538            function_scoped_bindings: true,
539            literals: Literals {
540                separators: Separators::BetweenDigits,
541                legacy_octal: LegacyOctal::Octal,
542                hex_floats: false,
543            },
544            ..Self::default()
545        }
546    }
547}
548
549impl Default for LangPolicy {
550    fn default() -> Self {
551        Self {
552            overflow: Overflow::Error,
553            div_zero: DivZero::Error,
554            shift: Shift::Error,
555            float_to_int: FloatToInt::Error,
556            throws: EffectMode::Declared,
557            yields: EffectMode::Declared,
558            asyncs: EffectMode::Declared,
559            implicit_locals: false,
560            ident_patterns: IdentPatterns::Ident,
561            place_args: PlaceArgs::Marked,
562            function_scoped_bindings: false,
563            literals: Literals::default(),
564            implicit_receiver: None,
565            break_levels: BreakLevels::Labels,
566            default_member_visibility: Vis::Private,
567        }
568    }
569}
570
571/// A host or intrinsic name stored in a mapping, from
572/// [`MappingBuilder::name`].
573///
574/// # Examples
575///
576/// ```
577/// let mut b = lower_lang::MappingBuilder::<u8>::new();
578/// let concat = b.name("mox.concat");
579/// assert_ne!(concat, b.name("mox.echo"));
580/// ```
581#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
582pub struct NameRef(pub(crate) u32);
583
584/// How the pieces of an [interpolated string](crate::Arch::Interp) become one
585/// string.
586///
587/// # Examples
588///
589/// ```
590/// use lower_lang::{Join, MappingBuilder};
591///
592/// let mut b = MappingBuilder::<u8>::new();
593/// let concat = b.name("mox.concat");
594/// // "a{$x}b" → mox.concat(mox.concat("a", x), "b")
595/// let fold = Join::Fold(concat);
596/// assert_ne!(fold, Join::Call(concat));
597/// ```
598#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
599#[non_exhaustive]
600pub enum Join {
601    /// A host function of two arguments, folded left:
602    /// `concat(concat(p0, p1), p2)` (PHP's `.`).
603    Fold(NameRef),
604    /// One call of a host function with every piece as an argument:
605    /// `interp(p0, p1, p2)` (one LSB call, no intermediate strings).
606    Call(NameRef),
607    /// A template: with exactly two expression holes it is folded left like
608    /// `Fold`; with exactly one argument-list hole it receives every piece at
609    /// once. Any other hole shape is refused by
610    /// [`build`](MappingBuilder::build)
611    /// ([`MappingError::BadJoin`]).
612    Template(TemplateId),
613}
614
615/// What an operator token lowers to.
616///
617/// # Examples
618///
619/// ```
620/// use hir_lang::{Op, OpKind, Overflow};
621/// use lower_lang::OpSpec;
622///
623/// let plus = OpSpec::Op(OpKind::Add);                       // language policy
624/// let wrapping = OpSpec::OpWith(Op::new(OpKind::Add).with_overflow(Overflow::Wrap));
625/// let plus_eq = OpSpec::Compound(OpKind::Add);              // `+=`
626/// assert_ne!(plus, wrapping);
627/// assert_ne!(plus, plus_eq);
628/// ```
629#[derive(Clone, Copy, Debug, PartialEq, Eq)]
630#[non_exhaustive]
631pub enum OpSpec {
632    /// An intrinsic op with the language's policies ([`LangPolicy`]).
633    Op(OpKind),
634    /// An intrinsic op with exactly this policy (`[semantics.ops] "/" = { op =
635    /// "div", zero = "trap" }`).
636    OpWith(Op),
637    /// Compound assignment (`+=`) with the language's policies.
638    Compound(OpKind),
639    /// Compound assignment with exactly this policy.
640    CompoundWith(Op),
641    /// Plain assignment (`=` as an operator).
642    Assign,
643    /// Reference assignment (`=&`).
644    RefAssign,
645    /// The operand itself (unary `+`).
646    Identity,
647    /// `&x` / `&mut x` as a prefix operator.
648    Borrow(hir_lang::BorrowKind),
649    /// `*x` as a prefix operator.
650    Deref,
651    /// `await x` (prefix) or `x.await` (postfix).
652    Await,
653    /// A template whose expression holes receive the operands, in order
654    /// (`&&`, `||`, `??`, `x++`).
655    Template(TemplateId),
656    /// A call of a host function with the operands as arguments (Mox `.`
657    /// string concatenation).
658    Extern(NameRef),
659    /// A named backend intrinsic applied to the operands.
660    Intrinsic(NameRef),
661    /// Compound assignment through a host function (`.=` as `mox.concat`):
662    /// `let_place p = target in p = f(p, value)`, so the place's operands are
663    /// evaluated once (HIR `LetPlace`).
664    CompoundExtern(NameRef),
665    /// Compound assignment through a named intrinsic (`**=` as `mox.pow`),
666    /// lowered like [`CompoundExtern`](Self::CompoundExtern).
667    CompoundIntrinsic(NameRef),
668    /// Compound assignment through a template with exactly two expression
669    /// holes, which receive the place alias and the value (`??=` through
670    /// [`coalesce`](crate::templates::coalesce)): `let_place p = target in p =
671    /// template(p, value)`.
672    CompoundTemplate(TemplateId),
673}
674
675impl OpSpec {
676    /// Whether this is a compound assignment through a non-OPS operator
677    /// (lowered through `let_place`).
678    pub(crate) const fn is_place_compound(self) -> bool {
679        matches!(
680            self,
681            Self::CompoundExtern(_) | Self::CompoundIntrinsic(_) | Self::CompoundTemplate(_)
682        )
683    }
684}
685
686/// Ops a compound assignment may use (HIR §8.2; `pow` since hir-lang 0.4).
687pub(crate) const fn compound_ok(kind: OpKind) -> bool {
688    matches!(
689        kind,
690        OpKind::Add
691            | OpKind::Sub
692            | OpKind::Mul
693            | OpKind::Div
694            | OpKind::FloorDiv
695            | OpKind::Rem
696            | OpKind::FloorMod
697            | OpKind::And
698            | OpKind::Or
699            | OpKind::Xor
700            | OpKind::Shl
701            | OpKind::Shr
702            | OpKind::Pow
703    )
704}
705
706/// Operator positions, for the tables and errors.
707///
708/// # Examples
709///
710/// ```
711/// use lower_lang::Fixity;
712///
713/// assert_eq!(Fixity::Binary.arity(), 2);
714/// ```
715#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
716pub enum Fixity {
717    /// Before the operand.
718    Prefix,
719    /// Between two operands.
720    Binary,
721    /// After the operand.
722    Postfix,
723}
724
725impl Fixity {
726    /// The number of operands.
727    ///
728    /// # Examples
729    ///
730    /// ```
731    /// assert_eq!(lower_lang::Fixity::Prefix.arity(), 1);
732    /// ```
733    #[must_use]
734    pub const fn arity(self) -> usize {
735        match self {
736            Self::Binary => 2,
737            Self::Prefix | Self::Postfix => 1,
738        }
739    }
740}
741
742/// Why a mapping was refused.
743///
744/// # Examples
745///
746/// ```
747/// use lower_lang::{Arch, MappingBuilder, MappingError, Pick};
748///
749/// let mut b = MappingBuilder::<u8>::new();
750/// b.node(1, Arch::If { cond: Pick::Absent, then: Pick::Nth(1), else_: Pick::Absent });
751/// assert_eq!(b.build().unwrap_err(), MappingError::MissingField { rule: 0, field: "cond" });
752/// ```
753#[derive(Clone, Copy, Debug, PartialEq, Eq)]
754#[non_exhaustive]
755pub enum MappingError {
756    /// Rule `rule` (in registration order) leaves a required field `Absent`.
757    MissingField {
758        /// The rule's registration index.
759        rule: usize,
760        /// The field.
761        field: &'static str,
762    },
763    /// A kind has two entries in a table that allows one (`table` names it:
764    /// "token role", "modifier", "root", "prefix operator", ...).
765    DuplicateKind {
766        /// The table.
767        table: &'static str,
768        /// The later entry's registration index in that table.
769        index: usize,
770    },
771    /// A type name is registered twice.
772    DuplicateTypeName {
773        /// The later entry's registration index.
774        index: usize,
775    },
776    /// A template id that this mapping did not issue (or, inside a template,
777    /// one not registered before it).
778    UnknownTemplate {
779        /// The id's index.
780        template: usize,
781    },
782    /// A node binds a template with the wrong number of picks.
783    HoleCount {
784        /// The rule's registration index.
785        rule: usize,
786        /// The template's hole count.
787        expected: usize,
788        /// The picks given.
789        found: usize,
790    },
791    /// An `apply` inside template `template` passes arguments that do not
792    /// match the applied template's holes (count, or kind, or `Absent` for a
793    /// required hole).
794    ApplyArgs {
795        /// The registering template's index.
796        template: usize,
797    },
798    /// An operator maps to a spec that cannot apply at its position: an op of
799    /// the wrong arity, a compound op HIR does not allow, a policy that does
800    /// not fit its op, assignment outside binary position, identity outside
801    /// unary position, or a template whose holes are not one expression per
802    /// operand.
803    BadOperator {
804        /// The operator's position.
805        fixity: Fixity,
806        /// Its registration index in that table.
807        index: usize,
808    },
809    /// A table outgrew its index type.
810    TooLarge,
811    /// Rule `rule` joins an interpolated string with a template whose holes
812    /// are neither two expressions nor one argument list.
813    BadJoin {
814        /// The rule's registration index.
815        rule: usize,
816    },
817    /// A text-keyed operator entry has an empty text.
818    EmptyOperatorText {
819        /// The operator's position.
820        fixity: Fixity,
821        /// Its registration index in the text table.
822        index: usize,
823    },
824    /// A per-archetype modifier entry
825    /// ([`modifier_in`](MappingBuilder::modifier_in)) names no archetype
826    /// ([`Arch::lsf_name`] lists the names).
827    UnknownArchetype {
828        /// Its registration index among the per-archetype modifiers.
829        index: usize,
830    },
831    /// [`LangPolicy::implicit_receiver`] is a [`NameRef`] this builder did
832    /// not issue.
833    UnknownName {
834        /// The name's index.
835        index: usize,
836    },
837}
838
839impl fmt::Display for MappingError {
840    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
841        match self {
842            Self::MissingField { rule, field } => {
843                write!(f, "rule {rule}: required field `{field}` has no pick")
844            }
845            Self::DuplicateKind { table, index } => {
846                write!(f, "{table} {index}: the kind already has an entry")
847            }
848            Self::DuplicateTypeName { index } => write!(f, "type name {index} is registered twice"),
849            Self::UnknownTemplate { template } => {
850                write!(f, "template {template} is not registered")
851            }
852            Self::HoleCount {
853                rule,
854                expected,
855                found,
856            } => write!(
857                f,
858                "rule {rule}: the template has {expected} holes, {found} picks given"
859            ),
860            Self::ApplyArgs { template } => {
861                write!(
862                    f,
863                    "template {template}: an `apply` does not match the applied template's holes"
864                )
865            }
866            Self::BadOperator { fixity, index } => {
867                write!(
868                    f,
869                    "{fixity:?} operator {index} maps to a spec that cannot apply there"
870                )
871            }
872            Self::TooLarge => f.write_str("a mapping table outgrew its index type"),
873            Self::BadJoin { rule } => write!(
874                f,
875                "rule {rule}: an interpolation template needs two expression holes or one argument-list hole"
876            ),
877            Self::EmptyOperatorText { fixity, index } => {
878                write!(f, "{fixity:?} operator text {index} is empty")
879            }
880            Self::UnknownArchetype { index } => write!(
881                f,
882                "per-archetype modifier {index} names no archetype (expected an LSF2 `arch` name such as `param` or `arg`)"
883            ),
884            Self::UnknownName { index } => write!(
885                f,
886                "the implicit receiver is name {index}, which this mapping did not store"
887            ),
888        }
889    }
890}
891
892impl core::error::Error for MappingError {}
893
894/// One node rule: an archetype, applied when `when` finds something (or
895/// always, when `when` is `Absent`).
896#[derive(Clone, Copy, Debug)]
897pub(crate) struct Rule<K> {
898    pub(crate) when: Pick<K>,
899    pub(crate) arch: Arch<K>,
900}
901
902/// A language's semantics as data: what each node kind means, what each token
903/// is, which operators map to what, and the templates for sugar.
904///
905/// # Examples
906///
907/// ```
908/// use lower_lang::{Arch, MappingBuilder, Pick, TokenRole};
909///
910/// const IDENT: u8 = 1;
911/// const LET: u8 = 2;
912/// let mut b = MappingBuilder::new();
913/// b.token(IDENT, TokenRole::Name);
914/// b.node(LET, Arch::Let {
915///     pat: Pick::Kind(IDENT),
916///     ty: Pick::Absent,
917///     init: Pick::Back(0),
918///     else_: Pick::Absent,
919///     mutable: false,
920///     hoist: false,
921/// });
922/// let mapping = b.build()?;
923/// assert_eq!(mapping.role_for(&IDENT), Some(TokenRole::Name));
924/// assert!(mapping.rule_for(&LET).is_some());
925/// # Ok::<(), lower_lang::MappingError>(())
926/// ```
927#[derive(Clone, Debug)]
928pub struct Mapping<K> {
929    pub(crate) rules: Vec<Rule<K>>,
930    pub(crate) by_kind: Vec<(K, u32)>,
931    pub(crate) roles: Vec<(K, TokenRole)>,
932    pub(crate) modifiers: Vec<(K, Modifier)>,
933    /// Modifiers that depend on the archetype they appear in (`...` is a
934    /// rest parameter in `param` and a spread in `arg`), sorted by kind;
935    /// they win over `modifiers` inside their archetype.
936    pub(crate) arch_modifiers: Vec<(K, &'static str, Modifier)>,
937    pub(crate) roots: Vec<(K, PathRoot)>,
938    pub(crate) containers: Vec<K>,
939    pub(crate) skips: Vec<K>,
940    pub(crate) errors: Vec<K>,
941    pub(crate) type_names: Vec<(Box<str>, TypeName)>,
942    pub(crate) suffixes: Vec<(Box<str>, Prim)>,
943    pub(crate) prefix: Vec<(K, OpSpec)>,
944    pub(crate) binary: Vec<(K, OpSpec)>,
945    pub(crate) postfix: Vec<(K, OpSpec)>,
946    /// Operator tables keyed by the token's text, consulted when the kind
947    /// table has no entry (lexers with one generic operator kind).
948    pub(crate) prefix_text: Vec<(Box<str>, OpSpec)>,
949    pub(crate) binary_text: Vec<(Box<str>, OpSpec)>,
950    pub(crate) postfix_text: Vec<(Box<str>, OpSpec)>,
951    /// Kinds with an `Attr` rule, sorted: invisible to other picks.
952    pub(crate) attr_kinds: Vec<K>,
953    pub(crate) templates: Vec<Template>,
954    pub(crate) template_names: Vec<u32>,
955    pub(crate) hole_picks: Vec<Pick<K>>,
956    pub(crate) strings: Vec<Box<str>>,
957    pub(crate) policy: LangPolicy,
958}
959
960fn find<'a, K: Ord, V>(table: &'a [(K, V)], kind: &K) -> Option<&'a V> {
961    table
962        .binary_search_by(|(k, _)| k.cmp(kind))
963        .ok()
964        .and_then(|i| table.get(i))
965        .map(|(_, v)| v)
966}
967
968impl<K: Copy + Ord> Mapping<K> {
969    /// The archetype of the first rule registered for `kind`.
970    ///
971    /// # Examples
972    ///
973    /// ```
974    /// use lower_lang::{Arch, MappingBuilder};
975    ///
976    /// let mut b = MappingBuilder::<u8>::new();
977    /// b.node(3, Arch::binary());
978    /// let m = b.build()?;
979    /// assert_eq!(m.rule_for(&3), Some(&Arch::binary()));
980    /// assert_eq!(m.rule_for(&4), None);
981    /// # Ok::<(), lower_lang::MappingError>(())
982    /// ```
983    #[must_use]
984    pub fn rule_for(&self, kind: &K) -> Option<&Arch<K>> {
985        let (start, _) = self.rule_range(kind);
986        self.by_kind
987            .get(start)
988            .filter(|(k, _)| k == kind)
989            .and_then(|(_, r)| self.rules.get(*r as usize))
990            .map(|r| &r.arch)
991    }
992
993    /// The role of token kind `kind`.
994    ///
995    /// # Examples
996    ///
997    /// See [`Mapping`].
998    #[must_use]
999    pub fn role_for(&self, kind: &K) -> Option<TokenRole> {
1000        find(&self.roles, kind).copied()
1001    }
1002
1003    /// The modifier token kind `kind` stands for.
1004    ///
1005    /// # Examples
1006    ///
1007    /// ```
1008    /// use lower_lang::{MappingBuilder, Modifier};
1009    ///
1010    /// let mut b = MappingBuilder::<u8>::new();
1011    /// b.modifier(9, Modifier::Mut);
1012    /// assert_eq!(b.build()?.modifier_for(&9), Some(Modifier::Mut));
1013    /// # Ok::<(), lower_lang::MappingError>(())
1014    /// ```
1015    #[must_use]
1016    pub fn modifier_for(&self, kind: &K) -> Option<Modifier> {
1017        find(&self.modifiers, kind).copied()
1018    }
1019
1020    /// The modifier token kind `kind` stands for inside archetype
1021    /// `archetype` (its [`Arch::lsf_name`]): the
1022    /// [per-archetype](MappingBuilder::modifier_in) entry, else the plain
1023    /// one ([`modifier_for`](Self::modifier_for)).
1024    ///
1025    /// # Examples
1026    ///
1027    /// ```
1028    /// use lower_lang::{MappingBuilder, Modifier};
1029    ///
1030    /// const DOTS: u8 = 7;
1031    /// let mut b = MappingBuilder::<u8>::new();
1032    /// b.modifier_in(DOTS, "param", Modifier::Rest)
1033    ///     .modifier_in(DOTS, "arg", Modifier::Spread);
1034    /// let m = b.build()?;
1035    /// assert_eq!(m.modifier_in(&DOTS, "param"), Some(Modifier::Rest));
1036    /// assert_eq!(m.modifier_in(&DOTS, "arg"), Some(Modifier::Spread));
1037    /// assert_eq!(m.modifier_in(&DOTS, "map_entry"), None);
1038    /// assert_eq!(m.modifier_for(&DOTS), None);
1039    /// # Ok::<(), lower_lang::MappingError>(())
1040    /// ```
1041    #[must_use]
1042    pub fn modifier_in(&self, kind: &K, archetype: &str) -> Option<Modifier> {
1043        self.arch_modifier(kind, archetype)
1044            .or_else(|| self.modifier_for(kind))
1045    }
1046
1047    /// The per-archetype entry for `kind` in `archetype`, if any.
1048    fn arch_modifier(&self, kind: &K, archetype: &str) -> Option<Modifier> {
1049        if self.arch_modifiers.is_empty() {
1050            return None;
1051        }
1052        let start = self.arch_modifiers.partition_point(|(k, _, _)| k < kind);
1053        self.arch_modifiers
1054            .get(start..)
1055            .unwrap_or(&[])
1056            .iter()
1057            .take_while(|(k, _, _)| k == kind)
1058            .find(|(_, a, _)| *a == archetype)
1059            .map(|(_, _, m)| *m)
1060    }
1061
1062    /// The registered template `id`.
1063    ///
1064    /// # Examples
1065    ///
1066    /// ```
1067    /// use lower_lang::{templates, MappingBuilder};
1068    ///
1069    /// let mut b = MappingBuilder::<u8>::new();
1070    /// let id = b.template(templates::coalesce())?;
1071    /// let m = b.build()?;
1072    /// assert_eq!(m.template(id).map(|t| t.name()), Some("??"));
1073    /// # Ok::<(), lower_lang::MappingError>(())
1074    /// ```
1075    #[must_use]
1076    pub fn template(&self, id: TemplateId) -> Option<&Template> {
1077        self.templates.get(id.index())
1078    }
1079
1080    /// The language-wide policies.
1081    ///
1082    /// # Examples
1083    ///
1084    /// ```
1085    /// use lower_lang::{LangPolicy, MappingBuilder};
1086    ///
1087    /// let m = MappingBuilder::<u8>::new().build()?;
1088    /// assert_eq!(*m.policy(), LangPolicy::default());
1089    /// # Ok::<(), lower_lang::MappingError>(())
1090    /// ```
1091    #[must_use]
1092    pub const fn policy(&self) -> &LangPolicy {
1093        &self.policy
1094    }
1095
1096    /// The rules registered for `kind`, as an index range into `by_kind`.
1097    pub(crate) fn rule_range(&self, kind: &K) -> (usize, usize) {
1098        let start = self.by_kind.partition_point(|(k, _)| k < kind);
1099        let end = start
1100            + self
1101                .by_kind
1102                .get(start..)
1103                .map_or(0, |rest| rest.partition_point(|(k, _)| k == kind));
1104        (start, end)
1105    }
1106
1107    /// The operator spec of a token: by kind first, then by its text.
1108    pub(crate) fn op(&self, fixity: Fixity, kind: &K, text: &str) -> Option<OpSpec> {
1109        let (table, texts) = match fixity {
1110            Fixity::Prefix => (&self.prefix, &self.prefix_text),
1111            Fixity::Binary => (&self.binary, &self.binary_text),
1112            Fixity::Postfix => (&self.postfix, &self.postfix_text),
1113        };
1114        find(table, kind).copied().or_else(|| {
1115            if texts.is_empty() {
1116                return None;
1117            }
1118            texts
1119                .binary_search_by(|(t, _)| (**t).cmp(text))
1120                .ok()
1121                .and_then(|i| texts.get(i))
1122                .map(|(_, s)| *s)
1123        })
1124    }
1125
1126    /// Whether the operator tables are keyed by text at all (so a lookup
1127    /// needs the token's text).
1128    pub(crate) fn has_op_text(&self) -> bool {
1129        !(self.prefix_text.is_empty()
1130            && self.binary_text.is_empty()
1131            && self.postfix_text.is_empty())
1132    }
1133
1134    pub(crate) fn root_for(&self, kind: &K) -> Option<PathRoot> {
1135        find(&self.roots, kind).copied()
1136    }
1137
1138    pub(crate) fn is_error(&self, kind: &K) -> bool {
1139        self.errors.binary_search(kind).is_ok()
1140    }
1141
1142    pub(crate) fn type_name(&self, text: &str) -> Option<TypeName> {
1143        self.type_names
1144            .binary_search_by(|(t, _)| (**t).cmp(text))
1145            .ok()
1146            .and_then(|i| self.type_names.get(i))
1147            .map(|(_, n)| *n)
1148    }
1149}
1150
1151impl<K: Ord> KindSets<K> for Mapping<K> {
1152    fn is_skip(&self, kind: &K) -> bool {
1153        self.skips.binary_search(kind).is_ok()
1154    }
1155    fn is_container(&self, kind: &K) -> bool {
1156        self.containers.binary_search(kind).is_ok()
1157    }
1158    fn is_attr(&self, kind: &K) -> bool {
1159        !self.attr_kinds.is_empty() && self.attr_kinds.binary_search(kind).is_ok()
1160    }
1161}
1162
1163/// Builds a [`Mapping`]. Every method records; [`build`](Self::build) checks
1164/// everything and sorts the tables.
1165///
1166/// # Examples
1167///
1168/// A calculator's semantics: statements, `let`, numbers, names, and `+ - * /`.
1169///
1170/// ```
1171/// use hir_lang::OpKind;
1172/// use lower_lang::{Arch, MappingBuilder, OpSpec, Pick, TokenRole};
1173///
1174/// #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
1175/// enum K { Program, Let, Binary, Ident, Number, Plus, Star, Eq, Semi }
1176///
1177/// let mut b = MappingBuilder::new();
1178/// b.node(K::Program, Arch::Module { name: Pick::Absent, items: Pick::Nodes });
1179/// b.node(K::Let, Arch::Let {
1180///     pat: Pick::Kind(K::Ident), ty: Pick::Absent, init: Pick::After(K::Eq),
1181///     else_: Pick::Absent, mutable: false, hoist: false,
1182/// });
1183/// b.node(K::Binary, Arch::binary());
1184/// b.token(K::Ident, TokenRole::Name);
1185/// b.token(K::Number, TokenRole::Number);
1186/// b.binary_op(K::Plus, OpSpec::Op(OpKind::Add));
1187/// b.binary_op(K::Star, OpSpec::Op(OpKind::Mul));
1188/// b.skip(K::Semi);
1189/// let mapping = b.build()?;
1190/// # let _ = mapping;
1191/// # Ok::<(), lower_lang::MappingError>(())
1192/// ```
1193#[derive(Clone, Debug)]
1194pub struct MappingBuilder<K> {
1195    m: Mapping<K>,
1196    rule_picks_error: Option<MappingError>,
1197    /// Registered templates by name (the latest registration of a name), for
1198    /// `apply:<name>` in template texts.
1199    template_index: BTreeMap<Box<str>, u32>,
1200    /// Per-archetype modifiers as registered (archetype names checked by
1201    /// `build`).
1202    arch_modifiers: Vec<(K, Box<str>, Modifier)>,
1203}
1204
1205impl<K: Copy + Ord> Default for MappingBuilder<K> {
1206    fn default() -> Self {
1207        Self::new()
1208    }
1209}
1210
1211impl<K: Copy + Ord> MappingBuilder<K> {
1212    /// An empty builder with the default [`LangPolicy`].
1213    ///
1214    /// # Examples
1215    ///
1216    /// ```
1217    /// let m = lower_lang::MappingBuilder::<u8>::new().build()?;
1218    /// assert!(m.rule_for(&0).is_none());
1219    /// # Ok::<(), lower_lang::MappingError>(())
1220    /// ```
1221    #[must_use]
1222    pub fn new() -> Self {
1223        Self {
1224            m: Mapping {
1225                rules: Vec::new(),
1226                by_kind: Vec::new(),
1227                roles: Vec::new(),
1228                modifiers: Vec::new(),
1229                arch_modifiers: Vec::new(),
1230                roots: Vec::new(),
1231                containers: Vec::new(),
1232                skips: Vec::new(),
1233                errors: Vec::new(),
1234                type_names: Vec::new(),
1235                suffixes: Vec::new(),
1236                prefix: Vec::new(),
1237                binary: Vec::new(),
1238                postfix: Vec::new(),
1239                prefix_text: Vec::new(),
1240                binary_text: Vec::new(),
1241                postfix_text: Vec::new(),
1242                attr_kinds: Vec::new(),
1243                templates: Vec::new(),
1244                template_names: Vec::new(),
1245                hole_picks: Vec::new(),
1246                strings: Vec::new(),
1247                policy: LangPolicy::default(),
1248            },
1249            rule_picks_error: None,
1250            template_index: BTreeMap::new(),
1251            arch_modifiers: Vec::new(),
1252        }
1253    }
1254
1255    fn add_rule(&mut self, kind: K, when: Pick<K>, arch: Arch<K>) -> &mut Self {
1256        match u32::try_from(self.m.rules.len()) {
1257            Ok(i) if i < NONE => {
1258                self.m.rules.push(Rule { when, arch });
1259                self.m.by_kind.push((kind, i));
1260            }
1261            _ => self.rule_picks_error = Some(MappingError::TooLarge),
1262        }
1263        self
1264    }
1265
1266    /// Nodes of `kind` mean `arch`.
1267    ///
1268    /// # Examples
1269    ///
1270    /// See [`MappingBuilder`].
1271    pub fn node(&mut self, kind: K, arch: Arch<K>) -> &mut Self {
1272        self.add_rule(kind, Pick::Absent, arch)
1273    }
1274
1275    /// Nodes of `kind` mean `arch` when `when` finds a child; otherwise the
1276    /// next rule for `kind` (in registration order) is tried. For grammars
1277    /// that put alternatives in one rule (`stmt = "'let' ... | expr ';'"`).
1278    /// A node no rule applies to is reported as unmapped.
1279    ///
1280    /// # Examples
1281    ///
1282    /// ```
1283    /// use lower_lang::{Arch, MappingBuilder, Pick};
1284    ///
1285    /// const STMT: u8 = 1;
1286    /// const LET: u8 = 2;
1287    /// let mut b = MappingBuilder::new();
1288    /// b.node_when(STMT, Pick::First(LET), Arch::Let {
1289    ///     pat: Pick::Nth(1), ty: Pick::Absent, init: Pick::Nth(3),
1290    ///     else_: Pick::Absent, mutable: false, hoist: false,
1291    /// });
1292    /// b.node(STMT, Arch::ExprStmt { expr: Pick::Nth(0) });
1293    /// assert!(b.build().is_ok());
1294    /// ```
1295    pub fn node_when(&mut self, kind: K, when: Pick<K>, arch: Arch<K>) -> &mut Self {
1296        self.add_rule(kind, when, arch)
1297    }
1298
1299    /// Tokens of `kind` mean `role`.
1300    ///
1301    /// # Examples
1302    ///
1303    /// See [`Mapping`].
1304    pub fn token(&mut self, kind: K, role: TokenRole) -> &mut Self {
1305        self.m.roles.push((kind, role));
1306        self
1307    }
1308
1309    /// Tokens of `kind` set `modifier` on the construct they appear in.
1310    ///
1311    /// # Examples
1312    ///
1313    /// See [`Mapping::modifier_for`].
1314    pub fn modifier(&mut self, kind: K, modifier: Modifier) -> &mut Self {
1315        self.m.modifiers.push((kind, modifier));
1316        self
1317    }
1318
1319    /// Tokens of `kind` set `modifier` on constructs of archetype
1320    /// `archetype` (its LSF2 name, [`Arch::lsf_name`]), overriding the
1321    /// plain [`modifier`](Self::modifier) entry there: LSF2's per-archetype
1322    /// value `"..." = { param = "rest", arg = "spread" }`, for a token whose
1323    /// meaning depends on the construct (PHP's `...` is a rest parameter in a
1324    /// parameter and a spread in an argument). Elsewhere the token sets the
1325    /// plain entry, or nothing.
1326    ///
1327    /// `Spread` on a [`MapEntry`](Arch::MapEntry) (`[...$a, 1]`) is reported
1328    /// as [`Unsupported`](crate::ProblemKind::Unsupported): HIR's map and
1329    /// array literals have no spread entry. Parameter-list markers
1330    /// (`NamedOnly`, `PositionalOnly` tokens standing alone) are read from
1331    /// the plain table only.
1332    ///
1333    /// # Errors
1334    ///
1335    /// [`build`](Self::build) refuses an unknown archetype name
1336    /// ([`MappingError::UnknownArchetype`]) and a kind given two entries for
1337    /// one archetype ([`MappingError::DuplicateKind`], table `"archetype
1338    /// modifier"`).
1339    ///
1340    /// # Examples
1341    ///
1342    /// See [`Mapping::modifier_in`].
1343    pub fn modifier_in(&mut self, kind: K, archetype: &str, modifier: Modifier) -> &mut Self {
1344        self.arch_modifiers.push((kind, archetype.into(), modifier));
1345        self
1346    }
1347
1348    /// Leading tokens of `kind` in a [`Path`](Arch::Path) set its root
1349    /// (`self` → `SelfModule`, `super` → `Super(1)` each, `Self` → `SelfType`,
1350    /// PHP `parent`/`static` → `ParentType`/`StaticType`, `::` → `Global`).
1351    ///
1352    /// # Examples
1353    ///
1354    /// ```
1355    /// use hir_lang::PathRoot;
1356    ///
1357    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1358    /// b.root(5, PathRoot::Super(1));
1359    /// assert!(b.build().is_ok());
1360    /// ```
1361    pub fn root(&mut self, kind: K, root: PathRoot) -> &mut Self {
1362        self.m.roots.push((kind, root));
1363        self
1364    }
1365
1366    /// Nodes of `kind` are containers: list picks splice their children in
1367    /// place (an `args` node inside a `call`, a `params` node inside a `fn`).
1368    ///
1369    /// # Examples
1370    ///
1371    /// ```
1372    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1373    /// b.container(7);
1374    /// assert!(b.build().is_ok());
1375    /// ```
1376    pub fn container(&mut self, kind: K) -> &mut Self {
1377        self.m.containers.push(kind);
1378        self
1379    }
1380
1381    /// Tokens (or nodes) of `kind` are punctuation that list picks leave out
1382    /// (`,`, `;`, `(`).
1383    ///
1384    /// # Examples
1385    ///
1386    /// ```
1387    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1388    /// b.skip(8);
1389    /// assert!(b.build().is_ok());
1390    /// ```
1391    pub fn skip(&mut self, kind: K) -> &mut Self {
1392        self.m.skips.push(kind);
1393        self
1394    }
1395
1396    /// Nodes of `kind` are syntax errors (lang-forge's `ERROR`): they lower to
1397    /// error forms with a [`SyntaxError`](crate::ProblemKind::SyntaxError)
1398    /// problem, whatever context they appear in.
1399    ///
1400    /// # Examples
1401    ///
1402    /// ```
1403    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1404    /// b.error(0);
1405    /// assert!(b.build().is_ok());
1406    /// ```
1407    pub fn error(&mut self, kind: K) -> &mut Self {
1408        self.m.errors.push(kind);
1409        self
1410    }
1411
1412    /// An identifier spelled `text` names this type (`int` → `i64`, `mixed`
1413    /// → any).
1414    ///
1415    /// # Examples
1416    ///
1417    /// ```
1418    /// use hir_lang::Prim;
1419    /// use lower_lang::TypeName;
1420    ///
1421    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1422    /// b.type_name("int", TypeName::Prim(Prim::I64));
1423    /// assert!(b.build().is_ok());
1424    /// ```
1425    pub fn type_name(&mut self, text: &str, name: TypeName) -> &mut Self {
1426        self.m.type_names.push((text.into(), name));
1427        self
1428    }
1429
1430    /// A numeric literal ending in `suffix` has that type (`10u8`).
1431    ///
1432    /// # Examples
1433    ///
1434    /// ```
1435    /// use hir_lang::Prim;
1436    ///
1437    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1438    /// b.suffix("u8", Prim::U8);
1439    /// assert!(b.build().is_ok());
1440    /// ```
1441    pub fn suffix(&mut self, suffix: &str, prim: Prim) -> &mut Self {
1442        self.m.suffixes.push((suffix.into(), prim));
1443        self
1444    }
1445
1446    /// A prefix operator.
1447    ///
1448    /// # Examples
1449    ///
1450    /// ```
1451    /// use hir_lang::OpKind;
1452    /// use lower_lang::OpSpec;
1453    ///
1454    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1455    /// b.prefix_op(1, OpSpec::Op(OpKind::Neg));
1456    /// assert!(b.build().is_ok());
1457    /// ```
1458    pub fn prefix_op(&mut self, kind: K, spec: OpSpec) -> &mut Self {
1459        self.m.prefix.push((kind, spec));
1460        self
1461    }
1462
1463    /// A binary operator.
1464    ///
1465    /// # Examples
1466    ///
1467    /// See [`MappingBuilder`].
1468    pub fn binary_op(&mut self, kind: K, spec: OpSpec) -> &mut Self {
1469        self.m.binary.push((kind, spec));
1470        self
1471    }
1472
1473    /// A postfix operator.
1474    ///
1475    /// # Examples
1476    ///
1477    /// ```
1478    /// use lower_lang::{templates, OpSpec};
1479    ///
1480    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1481    /// let inc = b.template(templates::post_increment())?;
1482    /// b.postfix_op(1, OpSpec::Template(inc));
1483    /// assert!(b.build().is_ok());
1484    /// # Ok::<(), lower_lang::MappingError>(())
1485    /// ```
1486    pub fn postfix_op(&mut self, kind: K, spec: OpSpec) -> &mut Self {
1487        self.m.postfix.push((kind, spec));
1488        self
1489    }
1490
1491    /// A prefix operator found by its token's **text** (`"-"`, `"!"`), for a
1492    /// lexer that gives every operator one generic kind. A kind entry for the
1493    /// token's kind ([`prefix_op`](Self::prefix_op)) wins over a text entry.
1494    ///
1495    /// # Examples
1496    ///
1497    /// ```
1498    /// use hir_lang::OpKind;
1499    /// use lower_lang::OpSpec;
1500    ///
1501    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1502    /// b.prefix_op_text("-", OpSpec::Op(OpKind::Neg));
1503    /// assert!(b.build().is_ok());
1504    /// ```
1505    pub fn prefix_op_text(&mut self, text: &str, spec: OpSpec) -> &mut Self {
1506        self.m.prefix_text.push((text.into(), spec));
1507        self
1508    }
1509
1510    /// A binary operator found by its token's text (`"+"`, `"."`, `"+="`).
1511    ///
1512    /// # Examples
1513    ///
1514    /// ```
1515    /// use hir_lang::OpKind;
1516    /// use lower_lang::OpSpec;
1517    ///
1518    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1519    /// b.binary_op_text("+", OpSpec::Op(OpKind::Add))
1520    ///     .binary_op_text("+=", OpSpec::Compound(OpKind::Add));
1521    /// assert!(b.build().is_ok());
1522    /// ```
1523    pub fn binary_op_text(&mut self, text: &str, spec: OpSpec) -> &mut Self {
1524        self.m.binary_text.push((text.into(), spec));
1525        self
1526    }
1527
1528    /// A postfix operator found by its token's text (`"++"`).
1529    ///
1530    /// # Examples
1531    ///
1532    /// ```
1533    /// use lower_lang::{templates, OpSpec};
1534    ///
1535    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1536    /// let inc = b.template(templates::post_increment())?;
1537    /// b.postfix_op_text("++", OpSpec::Template(inc));
1538    /// assert!(b.build().is_ok());
1539    /// # Ok::<(), lower_lang::MappingError>(())
1540    /// ```
1541    pub fn postfix_op_text(&mut self, text: &str, spec: OpSpec) -> &mut Self {
1542        self.m.postfix_text.push((text.into(), spec));
1543        self
1544    }
1545
1546    /// Stores a host or intrinsic name for [`OpSpec::Extern`] and
1547    /// [`OpSpec::Intrinsic`]; interned per lowering.
1548    ///
1549    /// # Examples
1550    ///
1551    /// See [`NameRef`].
1552    pub fn name(&mut self, text: &str) -> NameRef {
1553        NameRef(self.string(text))
1554    }
1555
1556    fn string(&mut self, text: &str) -> u32 {
1557        let i = self.m.strings.len();
1558        self.m.strings.push(text.into());
1559        u32::try_from(i).unwrap_or_else(|_| {
1560            self.rule_picks_error = Some(MappingError::TooLarge);
1561            0
1562        })
1563    }
1564
1565    /// Sets the language-wide policies.
1566    ///
1567    /// # Examples
1568    ///
1569    /// ```
1570    /// use lower_lang::LangPolicy;
1571    ///
1572    /// let mut policy = LangPolicy::default();
1573    /// policy.implicit_locals = true;
1574    /// let mut b = lower_lang::MappingBuilder::<u8>::new();
1575    /// b.policy(policy);
1576    /// assert!(b.build()?.policy().implicit_locals);
1577    /// # Ok::<(), lower_lang::MappingError>(())
1578    /// ```
1579    pub fn policy(&mut self, policy: LangPolicy) -> &mut Self {
1580        self.m.policy = policy;
1581        self
1582    }
1583
1584    /// Registers a template and returns its id. Templates it
1585    /// [`apply`](crate::TemplateBuilder::apply)s must already be registered,
1586    /// which keeps templates acyclic by construction.
1587    ///
1588    /// # Errors
1589    ///
1590    /// [`MappingError::UnknownTemplate`] if an `apply` names a template not
1591    /// registered before this one; [`MappingError::ApplyArgs`] if its
1592    /// arguments do not match that template's holes.
1593    ///
1594    /// # Examples
1595    ///
1596    /// ```
1597    /// use lower_lang::{templates, MappingBuilder};
1598    ///
1599    /// let mut b = MappingBuilder::<u8>::new();
1600    /// let id = b.template(templates::while_loop())?;
1601    /// assert_eq!(id.index(), 0);
1602    /// # Ok::<(), lower_lang::MappingError>(())
1603    /// ```
1604    pub fn template(&mut self, mut template: Template) -> Result<TemplateId, MappingError> {
1605        let index = self.m.templates.len();
1606        for &node in &template.applies {
1607            let Some(TNode::Apply {
1608                template: callee,
1609                args,
1610            }) = template.node(node).copied()
1611            else {
1612                continue;
1613            };
1614            let callee_t =
1615                self.m
1616                    .templates
1617                    .get(callee as usize)
1618                    .ok_or(MappingError::UnknownTemplate {
1619                        template: callee as usize,
1620                    })?;
1621            let (start, len) = (args.0 as usize, args.1 as usize);
1622            let given = template
1623                .args
1624                .get(start..start.saturating_add(len))
1625                .ok_or(MappingError::ApplyArgs { template: index })?;
1626            if given.len() != callee_t.holes.len() {
1627                return Err(MappingError::ApplyArgs { template: index });
1628            }
1629            for (arg, hole) in given.iter().zip(&callee_t.holes) {
1630                let fits = match arg.kind() {
1631                    Some(kind) => kind == hole.kind,
1632                    None => hole.optional,
1633                };
1634                let forwarded_ok = match *arg {
1635                    TArg::Stmts(h) => template
1636                        .holes
1637                        .get(usize::from(h.0))
1638                        .is_some_and(|d| d.kind == HoleKind::Stmts),
1639                    TArg::Args(h) => template
1640                        .holes
1641                        .get(usize::from(h.0))
1642                        .is_some_and(|d| d.kind == HoleKind::Args),
1643                    _ => true,
1644                };
1645                if !fits || !forwarded_ok {
1646                    return Err(MappingError::ApplyArgs { template: index });
1647                }
1648            }
1649        }
1650        let id = u32::try_from(index).map_err(|_| MappingError::TooLarge)?;
1651        let base = u32::try_from(self.m.strings.len()).map_err(|_| MappingError::TooLarge)?;
1652        template.text_base = base;
1653        self.m.strings.extend(template.texts.iter().cloned());
1654        let name = template.name.clone();
1655        let name_ref = self.string(&name);
1656        self.m.template_names.push(name_ref);
1657        self.m.templates.push(template);
1658        let _ = self.template_index.insert(name, id);
1659        Ok(TemplateId(id))
1660    }
1661
1662    /// Parses a template text ([`Template::parse`]) and registers it under
1663    /// `name`: the path for LSF2's `[semantics.templates]`, in document
1664    /// order. `apply:<name>(…)` in the text names a template registered
1665    /// before this one — by its name, or, for the built-ins of
1666    /// [`templates`](crate::templates), by its LSF2 name (`while`,
1667    /// `do_while`, `c_for`, `for_each`, `logical_and`, `logical_or`,
1668    /// `and_value`, `or_value`, `coalesce`, `try`, `post_increment`). When a
1669    /// name is registered twice, the later registration answers.
1670    ///
1671    /// # Errors
1672    ///
1673    /// [`TemplateError::Syntax`] for text that is not a valid template,
1674    /// including an `apply:` of an unknown template
1675    /// ([`SyntaxError::UnknownTemplate`]) or with arguments that do not fit
1676    /// its holes ([`SyntaxError::ApplyArgs`]); `TooLarge` when a table
1677    /// outgrows its index type.
1678    ///
1679    /// # Examples
1680    ///
1681    /// ```
1682    /// use lower_lang::{templates, MappingBuilder};
1683    ///
1684    /// let mut b = MappingBuilder::<u8>::new();
1685    /// let _coalesce = b.template(templates::coalesce())?;
1686    /// // `??` under another name, through the built-in.
1687    /// let elvis = b.parse_template("elvis", "apply:coalesce(${lhs}, ${rhs})")?;
1688    /// assert_eq!(elvis.index(), 1);
1689    /// # Ok::<(), Box<dyn std::error::Error>>(())
1690    /// ```
1691    pub fn parse_template(&mut self, name: &str, text: &str) -> Result<TemplateId, TemplateError> {
1692        let registry = Registry {
1693            templates: &self.m.templates,
1694            by_name: &self.template_index,
1695        };
1696        let template = text::parse(name, text, Some(registry))?;
1697        self.template(template).map_err(|e| match e {
1698            MappingError::TooLarge => TemplateError::TooLarge,
1699            // The parser checked every `apply` against this registry.
1700            _ => TemplateError::Syntax {
1701                at: hir_lang::Span::new(0, u32::try_from(text.len()).unwrap_or(u32::MAX)),
1702                error: SyntaxError::ApplyArgs,
1703            },
1704        })
1705    }
1706
1707    /// Nodes of `kind` lower through `template`, its holes filled from
1708    /// `holes` (one pick per hole, in the template's hole order).
1709    ///
1710    /// # Examples
1711    ///
1712    /// ```
1713    /// use lower_lang::{templates, MappingBuilder, Pick};
1714    ///
1715    /// const WHILE: u8 = 1;
1716    /// let mut b = MappingBuilder::new();
1717    /// let w = b.template(templates::while_loop())?;
1718    /// // `while COND BLOCK`: holes cond, body, label.
1719    /// b.template_node(WHILE, w, &[Pick::NthNode(0), Pick::NthNode(1), Pick::Absent]);
1720    /// assert!(b.build().is_ok());
1721    /// # Ok::<(), lower_lang::MappingError>(())
1722    /// ```
1723    pub fn template_node(&mut self, kind: K, template: TemplateId, holes: &[Pick<K>]) -> &mut Self {
1724        self.template_node_when(kind, Pick::Absent, template, holes)
1725    }
1726
1727    /// Nodes of `kind` lower through `template` when `when` finds a child;
1728    /// otherwise the next rule for `kind` (in registration order) is tried,
1729    /// as with [`node_when`](Self::node_when). LSF2's conditional template
1730    /// alternative `{ when = …, template = …, holes = … }` (ISSUES P40): PHP's
1731    /// `include` / `include_once` / `require` / `require_once` are one node
1732    /// kind told apart by their keyword.
1733    ///
1734    /// # Examples
1735    ///
1736    /// ```
1737    /// use lower_lang::{MappingBuilder, Pick};
1738    ///
1739    /// const INCLUDE_EXPR: u8 = 1;
1740    /// const REQUIRE_KW: u8 = 2;
1741    /// let mut b = MappingBuilder::new();
1742    /// let require = b.parse_template("require", "extern:mox.require(${path})")?;
1743    /// let include = b.parse_template("include", "extern:mox.include(${path})")?;
1744    /// // `require EXPR` / `include EXPR`: the path is the last child.
1745    /// b.template_node_when(INCLUDE_EXPR, Pick::Kind(REQUIRE_KW), require, &[Pick::Back(0)]);
1746    /// b.template_node(INCLUDE_EXPR, include, &[Pick::Back(0)]);
1747    /// assert!(b.build().is_ok());
1748    /// # Ok::<(), Box<dyn std::error::Error>>(())
1749    /// ```
1750    pub fn template_node_when(
1751        &mut self,
1752        kind: K,
1753        when: Pick<K>,
1754        template: TemplateId,
1755        holes: &[Pick<K>],
1756    ) -> &mut Self {
1757        let first = self.m.hole_picks.len();
1758        self.m.hole_picks.extend_from_slice(holes);
1759        match (u32::try_from(first), u32::try_from(holes.len())) {
1760            (Ok(first), Ok(len)) => self.add_rule(
1761                kind,
1762                when,
1763                Arch::Template(TemplateUse {
1764                    template,
1765                    first,
1766                    len,
1767                }),
1768            ),
1769            _ => {
1770                self.rule_picks_error = Some(MappingError::TooLarge);
1771                self
1772            }
1773        }
1774    }
1775
1776    /// Checks the mapping and returns it.
1777    ///
1778    /// # Errors
1779    ///
1780    /// A [`MappingError`]: a required field without a pick, a kind with two
1781    /// entries in a one-entry table (or a text with two entries in a text
1782    /// operator table), an unknown template or a wrong number of template
1783    /// picks, an operator spec that cannot apply where it is registered, an
1784    /// empty operator text, an interpolation join template of the wrong
1785    /// shape, a per-archetype modifier naming no archetype, or an implicit
1786    /// receiver name this builder did not store.
1787    ///
1788    /// # Examples
1789    ///
1790    /// See [`MappingBuilder`].
1791    pub fn build(mut self) -> Result<Mapping<K>, MappingError> {
1792        if let Some(e) = self.rule_picks_error {
1793            return Err(e);
1794        }
1795        if let Some(NameRef(i)) = self.m.policy.implicit_receiver {
1796            if i as usize >= self.m.strings.len() {
1797                return Err(MappingError::UnknownName { index: i as usize });
1798            }
1799        }
1800        let mut arch_mods = Vec::with_capacity(self.arch_modifiers.len());
1801        for (index, (kind, name, modifier)) in self.arch_modifiers.iter().enumerate() {
1802            let name =
1803                crate::arch::lsf_name_of(name).ok_or(MappingError::UnknownArchetype { index })?;
1804            arch_mods.push((*kind, name, *modifier, index));
1805        }
1806        arch_mods.sort_by(|a, b| a.0.cmp(&b.0).then(a.1.cmp(b.1)).then(a.3.cmp(&b.3)));
1807        if let Some(w) = arch_mods
1808            .windows(2)
1809            .find(|w| w[0].0 == w[1].0 && w[0].1 == w[1].1)
1810        {
1811            return Err(MappingError::DuplicateKind {
1812                table: "archetype modifier",
1813                index: w[1].3,
1814            });
1815        }
1816        self.m.arch_modifiers = arch_mods
1817            .into_iter()
1818            .map(|(k, a, m, _)| (k, a, m))
1819            .collect();
1820        let m = &mut self.m;
1821        for (i, rule) in m.rules.iter().enumerate() {
1822            if let Some(field) = missing_field(&rule.arch) {
1823                return Err(MappingError::MissingField { rule: i, field });
1824            }
1825            if let Arch::Template(used) = rule.arch {
1826                let t = m.templates.get(used.template.index()).ok_or(
1827                    MappingError::UnknownTemplate {
1828                        template: used.template.index(),
1829                    },
1830                )?;
1831                if t.holes.len() != used.len as usize {
1832                    return Err(MappingError::HoleCount {
1833                        rule: i,
1834                        expected: t.holes.len(),
1835                        found: used.len as usize,
1836                    });
1837                }
1838            }
1839            if let Arch::Interp {
1840                join: Join::Template(id),
1841                ..
1842            } = rule.arch
1843            {
1844                let t = m
1845                    .templates
1846                    .get(id.index())
1847                    .ok_or(MappingError::UnknownTemplate {
1848                        template: id.index(),
1849                    })?;
1850                let fold = t.holes.len() == 2 && t.holes.iter().all(|h| h.kind == HoleKind::Expr);
1851                let all = t.holes.len() == 1 && t.holes.iter().all(|h| h.kind == HoleKind::Args);
1852                if !fold && !all {
1853                    return Err(MappingError::BadJoin { rule: i });
1854                }
1855            }
1856        }
1857        for (fixity, table) in [
1858            (Fixity::Prefix, &m.prefix_text),
1859            (Fixity::Binary, &m.binary_text),
1860            (Fixity::Postfix, &m.postfix_text),
1861        ] {
1862            for (index, (text, spec)) in table.iter().enumerate() {
1863                if text.is_empty() {
1864                    return Err(MappingError::EmptyOperatorText { fixity, index });
1865                }
1866                if !op_fits(*spec, fixity, &m.templates) {
1867                    return Err(MappingError::BadOperator { fixity, index });
1868                }
1869            }
1870        }
1871        for (fixity, table) in [
1872            (Fixity::Prefix, &m.prefix),
1873            (Fixity::Binary, &m.binary),
1874            (Fixity::Postfix, &m.postfix),
1875        ] {
1876            for (index, (_, spec)) in table.iter().enumerate() {
1877                if !op_fits(*spec, fixity, &m.templates) {
1878                    return Err(MappingError::BadOperator { fixity, index });
1879                }
1880            }
1881        }
1882        m.by_kind.sort_by_key(|e| e.0);
1883        sort_unique(&mut m.roles, "token role")?;
1884        sort_unique(&mut m.modifiers, "modifier")?;
1885        sort_unique(&mut m.roots, "root")?;
1886        sort_unique(&mut m.prefix, "prefix operator")?;
1887        sort_unique(&mut m.binary, "binary operator")?;
1888        sort_unique(&mut m.postfix, "postfix operator")?;
1889        sort_unique_text(&mut m.prefix_text, "prefix operator text")?;
1890        sort_unique_text(&mut m.binary_text, "binary operator text")?;
1891        sort_unique_text(&mut m.postfix_text, "postfix operator text")?;
1892        let mut attrs: Vec<K> = m
1893            .by_kind
1894            .iter()
1895            .filter(|(_, r)| {
1896                m.rules
1897                    .get(*r as usize)
1898                    .is_some_and(|r| matches!(r.arch, Arch::Attr { .. }))
1899            })
1900            .map(|(k, _)| *k)
1901            .collect();
1902        attrs.sort();
1903        attrs.dedup();
1904        m.attr_kinds = attrs;
1905        m.containers.sort();
1906        m.containers.dedup();
1907        m.skips.sort();
1908        m.skips.dedup();
1909        m.errors.sort();
1910        m.errors.dedup();
1911        let mut names: Vec<(usize, &str)> = m
1912            .type_names
1913            .iter()
1914            .enumerate()
1915            .map(|(i, (t, _))| (i, &**t))
1916            .collect();
1917        names.sort_by(|a, b| a.1.cmp(b.1).then(a.0.cmp(&b.0)));
1918        if let Some(w) = names.windows(2).find(|w| w[0].1 == w[1].1) {
1919            return Err(MappingError::DuplicateTypeName { index: w[1].0 });
1920        }
1921        m.type_names.sort_by(|a, b| a.0.cmp(&b.0));
1922        // Longest suffix first, so `i64` wins over a hypothetical `4`.
1923        m.suffixes
1924            .sort_by(|a, b| b.0.len().cmp(&a.0.len()).then(a.0.cmp(&b.0)));
1925        Ok(self.m)
1926    }
1927}
1928
1929/// Sorts a kind-keyed table, refusing a kind with two entries (reported by
1930/// the later entry's registration index).
1931fn sort_unique<K: Ord + Copy, V>(
1932    table: &mut [(K, V)],
1933    name: &'static str,
1934) -> Result<(), MappingError> {
1935    let mut order: Vec<(K, usize)> = table
1936        .iter()
1937        .enumerate()
1938        .map(|(i, (k, _))| (*k, i))
1939        .collect();
1940    order.sort();
1941    if let Some(w) = order.windows(2).find(|w| w[0].0 == w[1].0) {
1942        return Err(MappingError::DuplicateKind {
1943            table: name,
1944            index: w[1].1,
1945        });
1946    }
1947    table.sort_by_key(|e| e.0);
1948    Ok(())
1949}
1950
1951/// Sorts a text-keyed table, refusing a text with two entries.
1952fn sort_unique_text<V>(
1953    table: &mut [(Box<str>, V)],
1954    name: &'static str,
1955) -> Result<(), MappingError> {
1956    let mut order: Vec<(&str, usize)> = table
1957        .iter()
1958        .enumerate()
1959        .map(|(i, (t, _))| (&**t, i))
1960        .collect();
1961    order.sort_unstable();
1962    if let Some(w) = order.windows(2).find(|w| w[0].0 == w[1].0) {
1963        return Err(MappingError::DuplicateKind {
1964            table: name,
1965            index: w[1].1,
1966        });
1967    }
1968    table.sort_by(|a, b| a.0.cmp(&b.0));
1969    Ok(())
1970}
1971
1972/// Whether `spec` can apply at `fixity`.
1973fn op_fits(spec: OpSpec, fixity: Fixity, templates: &[Template]) -> bool {
1974    let arity = fixity.arity();
1975    match spec {
1976        OpSpec::Op(kind) => kind.arity() == arity,
1977        OpSpec::OpWith(op) => op.kind.arity() == arity && op.policy_matches(),
1978        OpSpec::Compound(kind) => fixity == Fixity::Binary && compound_ok(kind),
1979        OpSpec::CompoundWith(op) => {
1980            fixity == Fixity::Binary && compound_ok(op.kind) && op.policy_matches()
1981        }
1982        OpSpec::Assign | OpSpec::RefAssign => fixity == Fixity::Binary,
1983        OpSpec::Identity | OpSpec::Await => fixity != Fixity::Binary,
1984        OpSpec::Borrow(_) | OpSpec::Deref => fixity == Fixity::Prefix,
1985        OpSpec::Template(id) => templates.get(id.index()).is_some_and(|t| {
1986            t.holes.len() == arity && t.holes.iter().all(|h| h.kind == HoleKind::Expr)
1987        }),
1988        OpSpec::Extern(_) | OpSpec::Intrinsic(_) => true,
1989        OpSpec::CompoundExtern(_) | OpSpec::CompoundIntrinsic(_) => fixity == Fixity::Binary,
1990        OpSpec::CompoundTemplate(id) => {
1991            fixity == Fixity::Binary
1992                && templates.get(id.index()).is_some_and(|t| {
1993                    t.holes.len() == 2 && t.holes.iter().all(|h| h.kind == HoleKind::Expr)
1994                })
1995        }
1996    }
1997}
1998
1999/// The first required field an archetype leaves `Absent`.
2000fn missing_field<K>(arch: &Arch<K>) -> Option<&'static str> {
2001    let need =
2002        |pairs: &[(&'static str, bool)]| pairs.iter().find(|(_, absent)| *absent).map(|(f, _)| *f);
2003    match arch {
2004        Arch::Module { .. }
2005        | Arch::Splice { .. }
2006        | Arch::Unsupported
2007        | Arch::GlobalDecl { .. }
2008        | Arch::MixinUse { .. }
2009        | Arch::UseTree { .. }
2010        | Arch::Interp { .. }
2011        | Arch::AttrArg { .. }
2012        | Arch::FieldDecl { .. }
2013        | Arch::Tuple { .. }
2014        | Arch::Array { .. }
2015        | Arch::Map { .. }
2016        | Arch::RecordLit { .. }
2017        | Arch::Block { .. }
2018        | Arch::Break { .. }
2019        | Arch::Continue { .. }
2020        | Arch::Return { .. }
2021        | Arch::Yield { .. }
2022        | Arch::Template(_)
2023        | Arch::WildPat
2024        | Arch::RestPat { .. }
2025        | Arch::TuplePat { .. }
2026        | Arch::RecordPat { .. }
2027        | Arch::OrPat { .. }
2028        | Arch::RangePat { .. }
2029        | Arch::SlicePat { .. }
2030        | Arch::TupleTy { .. }
2031        | Arch::FnTy { .. }
2032        | Arch::ObjectTy { .. }
2033        | Arch::ImplTy { .. }
2034        | Arch::UnionTy { .. }
2035        | Arch::IntersectionTy { .. } => None,
2036        Arch::Pass { inner } => need(&[("inner", inner.is_absent())]),
2037        Arch::Let { pat, .. } => need(&[("pat", pat.is_absent())]),
2038        Arch::ExprStmt { expr } => need(&[("expr", expr.is_absent())]),
2039        Arch::Defer { body } => need(&[("body", body.is_absent())]),
2040        Arch::Static { name, .. }
2041        | Arch::Fn { name, .. }
2042        | Arch::Record { name, .. }
2043        | Arch::Sum { name, .. }
2044        | Arch::Interface { name, .. }
2045        | Arch::Class { name, .. }
2046        | Arch::AssocType { name, .. }
2047        | Arch::Const { name, .. }
2048        | Arch::GlobalVar { name, .. }
2049        | Arch::VariantDecl { name, .. }
2050        | Arch::GenericParam { name, .. }
2051        | Arch::Capture { name }
2052        | Arch::Segment { name, .. }
2053        | Arch::BindPat { name, .. }
2054        | Arch::FieldPat { name, .. }
2055        | Arch::FieldInit { name, .. } => need(&[("name", name.is_absent())]),
2056        Arch::Import { path, .. } => need(&[("path", path.is_absent())]),
2057        Arch::MixinRule { method, .. } => need(&[("method", method.is_absent())]),
2058        Arch::Attr { name, .. } => need(&[("name", name.is_absent())]),
2059        Arch::Impl { self_ty, .. } => need(&[("self_ty", self_ty.is_absent())]),
2060        Arch::Alias { name, ty, .. } | Arch::AssocBinding { name, ty } => {
2061            need(&[("name", name.is_absent()), ("ty", ty.is_absent())])
2062        }
2063        Arch::WherePred { subject, .. } => need(&[("subject", subject.is_absent())]),
2064        Arch::Param { pat, .. } => need(&[("pat", pat.is_absent())]),
2065        Arch::Path {
2066            segments, qself, ..
2067        } => need(&[("segments", segments.is_absent() && qself.is_absent())]),
2068        Arch::Unary { op, operand } | Arch::Postfix { operand, op } => {
2069            need(&[("op", op.is_absent()), ("operand", operand.is_absent())])
2070        }
2071        Arch::Binary { lhs, op, rhs } => need(&[
2072            ("lhs", lhs.is_absent()),
2073            ("op", op.is_absent()),
2074            ("rhs", rhs.is_absent()),
2075        ]),
2076        Arch::Assign { target, value, .. } => {
2077            need(&[("target", target.is_absent()), ("value", value.is_absent())])
2078        }
2079        Arch::RefAssign { target, source } => need(&[
2080            ("target", target.is_absent()),
2081            ("source", source.is_absent()),
2082        ]),
2083        Arch::Call { callee, .. } => need(&[("callee", callee.is_absent())]),
2084        Arch::Arg { value, .. } | Arch::MapEntry { value, .. } => {
2085            need(&[("value", value.is_absent())])
2086        }
2087        Arch::Member { base, member, .. } => {
2088            need(&[("base", base.is_absent()), ("member", member.is_absent())])
2089        }
2090        Arch::MethodCall {
2091            receiver, method, ..
2092        } => need(&[
2093            ("receiver", receiver.is_absent()),
2094            ("method", method.is_absent()),
2095        ]),
2096        Arch::DynMember { base, name, .. } => {
2097            need(&[("base", base.is_absent()), ("name", name.is_absent())])
2098        }
2099        Arch::Index { base, index } => {
2100            need(&[("base", base.is_absent()), ("index", index.is_absent())])
2101        }
2102        Arch::VarVar { inner }
2103        | Arch::Deref { inner }
2104        | Arch::Await { inner }
2105        | Arch::YieldFrom { inner }
2106        | Arch::Spawn { inner }
2107        | Arch::RefPat { inner }
2108        | Arch::PtrTy { inner }
2109        | Arch::NullableTy { inner }
2110        | Arch::RefTy { inner, .. } => need(&[("inner", inner.is_absent())]),
2111        Arch::Append { base } => need(&[("base", base.is_absent())]),
2112        Arch::Repeat { elem, count } => {
2113            need(&[("elem", elem.is_absent()), ("count", count.is_absent())])
2114        }
2115        Arch::Cast { expr, ty } => need(&[("expr", expr.is_absent()), ("ty", ty.is_absent())]),
2116        Arch::Borrow { expr } => need(&[("expr", expr.is_absent())]),
2117        Arch::If { cond, then, .. } => {
2118            need(&[("cond", cond.is_absent()), ("then", then.is_absent())])
2119        }
2120        Arch::Match { scrutinee, .. } => need(&[("scrutinee", scrutinee.is_absent())]),
2121        Arch::Arm { pat, body, .. } => {
2122            need(&[("pat", pat.is_absent()), ("body", body.is_absent())])
2123        }
2124        Arch::Loop { body, .. }
2125        | Arch::Try { body, .. }
2126        | Arch::Catch { body, .. }
2127        | Arch::Closure { body, .. } => need(&[("body", body.is_absent())]),
2128        Arch::Throw { value } => need(&[("value", value.is_absent())]),
2129        Arch::CtorPat { path, .. } => need(&[("path", path.is_absent())]),
2130        Arch::TypeTestPat { ty, .. } => need(&[("ty", ty.is_absent())]),
2131        Arch::ArrayTy { elem, len } => {
2132            need(&[("elem", elem.is_absent()), ("len", len.is_absent())])
2133        }
2134        Arch::SliceTy { elem } => need(&[("elem", elem.is_absent())]),
2135    }
2136}
2137
2138/// The modifier bit a token of `kind` sets inside archetype `arch` (its LSF2
2139/// name; `None` when the mapping has no per-archetype entries), for the scan
2140/// of a node's children.
2141pub(crate) fn modifier_bits<K: Copy + Ord>(map: &Mapping<K>, kind: &K, arch: Option<&str>) -> u32 {
2142    if let Some(m) = arch.and_then(|a| map.arch_modifier(kind, a)) {
2143        return m.bit();
2144    }
2145    find(&map.modifiers, kind).map_or(0, |m| m.bit())
2146}
2147
2148#[cfg(test)]
2149// Builder methods return `&mut Self` for chaining; the tests discard it.
2150#[allow(unused_results)]
2151mod tests {
2152    use super::*;
2153    use crate::templates;
2154
2155    #[test]
2156    fn test_duplicate_roles_are_refused() {
2157        let mut b = MappingBuilder::<u8>::new();
2158        b.token(1, TokenRole::Name).token(1, TokenRole::Int);
2159        assert_eq!(
2160            b.build().err(),
2161            Some(MappingError::DuplicateKind {
2162                table: "token role",
2163                index: 1
2164            })
2165        );
2166    }
2167
2168    #[test]
2169    fn test_operator_specs_are_checked_against_their_position() {
2170        let mut b = MappingBuilder::<u8>::new();
2171        b.binary_op(1, OpSpec::Op(OpKind::Neg));
2172        assert!(matches!(b.build(), Err(MappingError::BadOperator { .. })));
2173
2174        let mut b = MappingBuilder::<u8>::new();
2175        b.binary_op(1, OpSpec::Compound(OpKind::Eq));
2176        assert!(matches!(b.build(), Err(MappingError::BadOperator { .. })));
2177
2178        let mut b = MappingBuilder::<u8>::new();
2179        b.prefix_op(1, OpSpec::Assign);
2180        assert!(matches!(b.build(), Err(MappingError::BadOperator { .. })));
2181
2182        let mut b = MappingBuilder::<u8>::new();
2183        let w = b.template(templates::while_loop()).ok();
2184        if let Some(w) = w {
2185            b.binary_op(1, OpSpec::Template(w));
2186        }
2187        assert!(matches!(b.build(), Err(MappingError::BadOperator { .. })));
2188    }
2189
2190    #[test]
2191    fn test_template_node_checks_hole_count() {
2192        let mut b = MappingBuilder::<u8>::new();
2193        let Ok(w) = b.template(templates::while_loop()) else {
2194            panic!("registers");
2195        };
2196        b.template_node(1, w, &[Pick::Nth(0)]);
2197        assert_eq!(
2198            b.build().err(),
2199            Some(MappingError::HoleCount {
2200                rule: 0,
2201                expected: 3,
2202                found: 1
2203            })
2204        );
2205    }
2206
2207    #[test]
2208    fn test_conditional_rules_keep_registration_order() {
2209        let mut b = MappingBuilder::<u8>::new();
2210        b.node(9, Arch::WildPat);
2211        b.node_when(4, Pick::First(1), Arch::Unsupported);
2212        b.node(4, Arch::WildPat);
2213        let Ok(m) = b.build() else { panic!("valid") };
2214        let (s, e) = m.rule_range(&4);
2215        assert_eq!(e - s, 2);
2216        assert_eq!(m.rule_for(&4), Some(&Arch::Unsupported));
2217    }
2218
2219    #[test]
2220    fn test_duplicate_type_names_are_refused() {
2221        let mut b = MappingBuilder::<u8>::new();
2222        b.type_name("int", TypeName::Any)
2223            .type_name("int", TypeName::Never);
2224        assert_eq!(
2225            b.build().err(),
2226            Some(MappingError::DuplicateTypeName { index: 1 })
2227        );
2228    }
2229}