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