Skip to main content

macro_lang/
definition.rs

1//! Macro definitions: rules, and the validated, compiled macro built from them.
2
3use alloc::vec::Vec;
4use core::fmt;
5
6use intern_lang::Symbol;
7
8use crate::compile::{CompiledRule, compile_rule};
9use crate::{MacroError, Pattern, Template};
10
11/// One arm of a macro: a pattern to match and the template it expands to.
12///
13/// A rule is plain data. [`Macro::new`] validates it and compiles it into the
14/// form the [`Expander`](crate::Expander) runs.
15///
16/// # Examples
17///
18/// `($x:tt) => { $x $x }` — duplicate a single tree:
19///
20/// ```
21/// use macro_lang::{Fragment, Pattern, Rule, Template};
22/// use intern_lang::Interner;
23///
24/// let mut names = Interner::new();
25/// let x = names.intern("x");
26/// let rule: Rule<char> = Rule {
27///     pattern: vec![Pattern::Bind { name: x, fragment: Fragment::Tree }],
28///     template: vec![Template::Var(x), Template::Var(x)],
29/// };
30/// assert_eq!(rule.template.len(), 2);
31/// ```
32#[derive(Clone, Debug)]
33pub struct Rule<K> {
34    /// What an invocation must look like for this rule to apply. It must match
35    /// the invocation's trees in full.
36    pub pattern: Vec<Pattern<K>>,
37    /// What the invocation expands to when the pattern matches.
38    pub template: Vec<Template<K>>,
39}
40
41/// A validated, compiled macro: a name and an ordered list of rules.
42///
43/// Building a `Macro` does all the work that does not depend on an invocation:
44/// it checks every rule (see [`MacroError`]) and compiles each pattern into a
45/// matching automaton and each template into a flat program. A macro is
46/// immutable once built and can be expanded any number of times, by any number
47/// of [`Expander`](crate::Expander)s.
48///
49/// When expanded, the rules are tried in order and the first rule whose pattern
50/// matches the invocation is used, exactly like the arms of `macro_rules!`.
51///
52/// # Examples
53///
54/// A two-rule macro: `()` expands to `0`, anything else is passed through.
55///
56/// ```
57/// use macro_lang::{Fragment, Kleene, Macro, Pattern, Rule, Template};
58/// use intern_lang::Interner;
59/// use token_lang::Span;
60///
61/// let mut names = Interner::new();
62/// let t = names.intern("t");
63/// let mac: Macro<char> = Macro::new(names.intern("or_zero"), vec![
64///     Rule { pattern: vec![], template: vec![Template::token('0', Span::new(0, 1))] },
65///     Rule {
66///         pattern: vec![Pattern::Repeat {
67///             body: vec![Pattern::Bind { name: t, fragment: Fragment::Tree }],
68///             separator: None,
69///             kleene: Kleene::OneOrMore,
70///         }],
71///         template: vec![Template::Repeat { body: vec![Template::Var(t)], separator: None }],
72///     },
73/// ])?;
74/// assert_eq!(mac.name(), names.intern("or_zero"));
75/// # Ok::<(), macro_lang::MacroError>(())
76/// ```
77#[derive(Clone)]
78pub struct Macro<K> {
79    name: Symbol,
80    rules: Vec<CompiledRule<K>>,
81}
82
83impl<K> Macro<K> {
84    /// Validates and compiles a macro from its rules.
85    ///
86    /// # Parameters
87    ///
88    /// - `name` — the macro's name. It is recorded in the
89    ///   [`Origin`](crate::Origin) of every context the macro's expansions mint,
90    ///   so diagnostics can say which macro introduced a token.
91    /// - `rules` — the arms, in the order they are tried.
92    ///
93    /// # Errors
94    ///
95    /// Returns the first problem found, checking rules in order:
96    ///
97    /// - [`MacroError::NoRules`] if `rules` is empty.
98    /// - [`MacroError::DuplicateBinding`] if a pattern binds a name twice.
99    /// - [`MacroError::EmptyRepetition`] if a pattern repetition can match
100    ///   nothing.
101    /// - [`MacroError::OptionalSeparator`] if a `?` repetition has a separator.
102    /// - [`MacroError::UnboundVariable`] if a template uses a name the pattern
103    ///   does not bind.
104    /// - [`MacroError::StillRepeating`] if a template uses a repeating
105    ///   metavariable outside enough repetitions.
106    /// - [`MacroError::NoRepeatingVariable`] if a template repetition has nothing
107    ///   to repeat over.
108    ///
109    /// # Examples
110    ///
111    /// ```
112    /// use macro_lang::{Fragment, Kleene, Macro, MacroError, Pattern, Rule, Template};
113    /// use intern_lang::Interner;
114    ///
115    /// let mut names = Interner::new();
116    /// let x = names.intern("x");
117    ///
118    /// // `$($x:tt)*` captured `x` inside a repetition, so the template cannot
119    /// // use it bare.
120    /// let err = Macro::<char>::new(names.intern("m"), vec![Rule {
121    ///     pattern: vec![Pattern::Repeat {
122    ///         body: vec![Pattern::Bind { name: x, fragment: Fragment::Tree }],
123    ///         separator: None,
124    ///         kleene: Kleene::ZeroOrMore,
125    ///     }],
126    ///     template: vec![Template::Var(x)],
127    /// }]).unwrap_err();
128    /// assert_eq!(err, MacroError::StillRepeating { rule: 0, name: x });
129    ///
130    /// assert_eq!(Macro::<char>::new(x, vec![]).unwrap_err(), MacroError::NoRules);
131    /// ```
132    pub fn new(name: Symbol, rules: Vec<Rule<K>>) -> Result<Self, MacroError> {
133        if rules.is_empty() {
134            return Err(MacroError::NoRules);
135        }
136        let rules = rules
137            .into_iter()
138            .enumerate()
139            .map(|(index, rule)| compile_rule(rule, index))
140            .collect::<Result<Vec<_>, _>>()?;
141        Ok(Self { name, rules })
142    }
143
144    /// Returns the macro's name.
145    ///
146    /// # Examples
147    ///
148    /// ```
149    /// use macro_lang::{Macro, Rule};
150    /// use intern_lang::Interner;
151    ///
152    /// let mut names = Interner::new();
153    /// let empty = names.intern("empty");
154    /// let mac: Macro<char> = Macro::new(empty, vec![Rule { pattern: vec![], template: vec![] }])?;
155    /// assert_eq!(names.resolve(mac.name()), Some("empty"));
156    /// # Ok::<(), macro_lang::MacroError>(())
157    /// ```
158    #[inline]
159    #[must_use]
160    pub const fn name(&self) -> Symbol {
161        self.name
162    }
163
164    /// The compiled rules, in the order they are tried.
165    #[inline]
166    pub(crate) fn rules(&self) -> &[CompiledRule<K>] {
167        &self.rules
168    }
169}
170
171impl<K> fmt::Debug for Macro<K> {
172    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
173        f.debug_struct("Macro")
174            .field("name", &self.name)
175            .field("rules", &self.rules.len())
176            .finish()
177    }
178}
179
180#[cfg(test)]
181mod tests {
182    #![allow(clippy::unwrap_used)]
183
184    use alloc::format;
185    use alloc::vec;
186
187    use token_lang::{Span, Token};
188
189    use super::*;
190    use crate::compile::{Inst, Op};
191    use crate::{Fragment, Kleene};
192
193    fn sym(n: u32) -> Symbol {
194        Symbol::from_u32(n).unwrap()
195    }
196
197    fn bind(n: u32) -> Pattern<u8> {
198        Pattern::Bind {
199            name: sym(n),
200            fragment: Fragment::Tree,
201        }
202    }
203
204    fn repeat(body: Vec<Pattern<u8>>, separator: Option<u8>, kleene: Kleene) -> Pattern<u8> {
205        Pattern::Repeat {
206            body,
207            separator,
208            kleene,
209        }
210    }
211
212    fn one(
213        pattern: Vec<Pattern<u8>>,
214        template: Vec<Template<u8>>,
215    ) -> Result<Macro<u8>, MacroError> {
216        Macro::new(sym(100), vec![Rule { pattern, template }])
217    }
218
219    #[test]
220    fn test_rejects_no_rules() {
221        assert_eq!(
222            Macro::<u8>::new(sym(1), vec![]).unwrap_err(),
223            MacroError::NoRules
224        );
225    }
226
227    #[test]
228    fn test_rejects_duplicate_binding_in_nested_position() {
229        let pattern = vec![bind(1), repeat(vec![bind(1)], None, Kleene::ZeroOrMore)];
230        assert_eq!(
231            one(pattern, vec![]).unwrap_err(),
232            MacroError::DuplicateBinding {
233                rule: 0,
234                name: sym(1)
235            }
236        );
237    }
238
239    #[test]
240    fn test_rejects_unbound_variable() {
241        assert_eq!(
242            one(vec![], vec![Template::Var(sym(9))]).unwrap_err(),
243            MacroError::UnboundVariable {
244                rule: 0,
245                name: sym(9)
246            }
247        );
248    }
249
250    #[test]
251    fn test_rejects_empty_repetition_bodies() {
252        let empty = repeat(vec![], None, Kleene::ZeroOrMore);
253        assert_eq!(
254            one(vec![empty], vec![]).unwrap_err(),
255            MacroError::EmptyRepetition { rule: 0 }
256        );
257
258        // A body made only of optional parts can still match nothing.
259        let nullable = repeat(
260            vec![repeat(vec![Pattern::Token(1)], None, Kleene::ZeroOrOne)],
261            None,
262            Kleene::OneOrMore,
263        );
264        assert_eq!(
265            one(vec![nullable], vec![]).unwrap_err(),
266            MacroError::EmptyRepetition { rule: 0 }
267        );
268    }
269
270    #[test]
271    fn test_accepts_body_whose_inner_repetition_requires_input() {
272        let inner = repeat(vec![Pattern::Token(1)], None, Kleene::OneOrMore);
273        let outer = repeat(vec![inner], Some(2), Kleene::ZeroOrMore);
274        assert!(one(vec![outer], vec![]).is_ok());
275    }
276
277    #[test]
278    fn test_accepts_group_with_empty_body_in_repetition() {
279        let group = Pattern::Group {
280            open: 1,
281            close: 2,
282            body: vec![],
283        };
284        assert!(one(vec![repeat(vec![group], None, Kleene::ZeroOrMore)], vec![]).is_ok());
285    }
286
287    #[test]
288    fn test_rejects_optional_separator() {
289        let pattern = vec![repeat(vec![bind(1)], Some(0), Kleene::ZeroOrOne)];
290        assert_eq!(
291            one(pattern, vec![]).unwrap_err(),
292            MacroError::OptionalSeparator { rule: 0 }
293        );
294    }
295
296    #[test]
297    fn test_rejects_shallow_use_of_repeating_variable() {
298        let pattern = vec![repeat(vec![bind(1)], None, Kleene::ZeroOrMore)];
299        assert_eq!(
300            one(pattern, vec![Template::Var(sym(1))]).unwrap_err(),
301            MacroError::StillRepeating {
302                rule: 0,
303                name: sym(1)
304            }
305        );
306    }
307
308    #[test]
309    fn test_rejects_repetition_without_repeating_variable() {
310        let template = vec![Template::Repeat {
311            body: vec![Template::Var(sym(1))],
312            separator: None,
313        }];
314        assert_eq!(
315            one(vec![bind(1)], template).unwrap_err(),
316            MacroError::NoRepeatingVariable { rule: 0 }
317        );
318    }
319
320    #[test]
321    fn test_reports_the_failing_rule_index() {
322        let rules: Vec<Rule<u8>> = vec![
323            Rule {
324                pattern: vec![],
325                template: vec![],
326            },
327            Rule {
328                pattern: vec![],
329                template: vec![Template::Var(sym(5))],
330            },
331        ];
332        assert_eq!(
333            Macro::new(sym(1), rules).unwrap_err(),
334            MacroError::UnboundVariable {
335                rule: 1,
336                name: sym(5)
337            }
338        );
339    }
340
341    #[test]
342    fn test_star_with_separator_program_shape() {
343        let mac = one(
344            vec![repeat(vec![Pattern::Token(7)], Some(9), Kleene::ZeroOrMore)],
345            vec![],
346        )
347        .unwrap();
348        let program = &mac.rules()[0].program;
349        // Enter, Split(I, X), I: Iter, body, Split(S, X), S: sep, Jump(I), X: Accept
350        assert!(matches!(program[0], Inst::Enter(0)));
351        assert!(matches!(program[1], Inst::Split(2, 7)));
352        assert!(matches!(program[2], Inst::Iter(0)));
353        assert!(matches!(program[3], Inst::Token(7)));
354        assert!(matches!(program[4], Inst::Split(5, 7)));
355        assert!(matches!(program[5], Inst::Token(9)));
356        assert!(matches!(program[6], Inst::Jump(2)));
357        assert!(matches!(program[7], Inst::Accept));
358    }
359
360    #[test]
361    fn test_template_repeat_is_patched_with_end_and_locks() {
362        let pattern = vec![repeat(vec![bind(1), bind(2)], None, Kleene::ZeroOrMore)];
363        let template = vec![Template::Repeat {
364            body: vec![
365                Template::Var(sym(1)),
366                Template::Var(sym(2)),
367                Template::Var(sym(1)),
368            ],
369            separator: Some(Token::new(3, Span::new(0, 1))),
370        }];
371        let mac = one(pattern, template).unwrap();
372        let rule = &mac.rules()[0];
373        assert!(matches!(
374            rule.ops[0],
375            Op::Repeat {
376                end: 4,
377                locks: (0, 2),
378                ..
379            }
380        ));
381        assert!(matches!(rule.ops[4], Op::End { start: 0 }));
382        assert_eq!(rule.locks, vec![0, 1]);
383        assert_eq!(rule.chain(0), &[0]);
384    }
385
386    #[test]
387    fn test_debug_shows_name_and_rule_count() {
388        let mac = one(vec![], vec![]).unwrap();
389        assert_eq!(format!("{mac:?}"), "Macro { name: Symbol(100), rules: 1 }");
390    }
391}