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}