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}