macro_lang/context.rs
1//! Hygiene: syntax contexts, their origins, and the table that records them.
2//!
3//! Every token in a [`Tree`](crate::Tree) carries a [`Context`]. Tokens that came
4//! straight from source carry [`Context::ROOT`]. Each expansion mints a fresh
5//! context for the tokens its template introduces, while tokens substituted from
6//! the invocation keep the context they arrived with. A name resolver that treats
7//! two identifiers as the same binding only when both their name and their context
8//! match gets hygiene for free: a temporary introduced by a macro can never capture,
9//! or be captured by, a same-named variable at the call site.
10
11use alloc::vec::Vec;
12use core::fmt;
13
14use intern_lang::Symbol;
15use token_lang::Span;
16
17/// The hygiene context of a token: which expansion, if any, introduced it.
18///
19/// A context is a small copyable handle. [`Context::ROOT`] is the context of
20/// every token written directly in source; every other context is minted by an
21/// [`Expander`](crate::Expander) when a macro's template introduces a token, and
22/// the expander can report where it came from through
23/// [`origin`](crate::Expander::origin).
24///
25/// Two identifiers with the same spelling denote the same binding only if their
26/// contexts are equal too. That single rule is what keeps a macro's internal
27/// names from colliding with the names at its call site.
28///
29/// Contexts are only meaningful to the expander that minted them; a context
30/// from one expander carries no information in another.
31///
32/// # Examples
33///
34/// ```
35/// use macro_lang::Context;
36///
37/// let ctx = Context::ROOT;
38/// assert!(ctx.is_root());
39/// assert_eq!(ctx.as_u32(), 0);
40/// assert_eq!(ctx.to_string(), "#0");
41/// ```
42#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
43pub struct Context(u32);
44
45impl Context {
46 /// The context of tokens written directly in source, introduced by no
47 /// expansion.
48 pub const ROOT: Self = Self(0);
49
50 /// Returns `true` for [`Context::ROOT`] — a token no expansion introduced.
51 ///
52 /// # Examples
53 ///
54 /// ```
55 /// use macro_lang::Context;
56 ///
57 /// assert!(Context::ROOT.is_root());
58 /// assert!(Context::default().is_root());
59 /// ```
60 #[inline]
61 #[must_use]
62 pub const fn is_root(self) -> bool {
63 self.0 == 0
64 }
65
66 /// Returns the raw index of this context.
67 ///
68 /// Contexts are numbered densely from `0` (the root) in the order an
69 /// expander mints them, so the index is suitable as a key into a side table.
70 ///
71 /// # Examples
72 ///
73 /// ```
74 /// use macro_lang::Context;
75 ///
76 /// assert_eq!(Context::ROOT.as_u32(), 0);
77 /// ```
78 #[inline]
79 #[must_use]
80 pub const fn as_u32(self) -> u32 {
81 self.0
82 }
83}
84
85impl fmt::Display for Context {
86 /// Formats the context as `#n`, the notation rustc uses for syntax contexts.
87 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
88 write!(f, "#{}", self.0)
89 }
90}
91
92/// Where a non-root [`Context`] came from: the expansion that minted it.
93///
94/// Returned by [`Expander::origin`](crate::Expander::origin). The fields answer
95/// the two questions a later phase asks about a macro-introduced token: *how
96/// should its name resolve*, and *how did it get here*.
97///
98/// The struct is `#[non_exhaustive]`: only the expander builds one, and new
99/// fields may be added in a minor release. Read the fields directly, or
100/// destructure with a trailing `..`.
101///
102/// # Examples
103///
104/// ```
105/// use macro_lang::{Context, Expander, Fragment, Macro, Pattern, Rule, Template, Tree};
106/// use intern_lang::Interner;
107/// use token_lang::Span;
108///
109/// let mut names = Interner::new();
110/// let id = names.intern("id");
111///
112/// // A macro whose template introduces a single token: `0`.
113/// let mac: Macro<char> = Macro::new(id, vec![Rule {
114/// pattern: vec![],
115/// template: vec![Template::token('0', Span::new(20, 21))],
116/// }])?;
117///
118/// let mut expander = Expander::new();
119/// let out = expander.expand(&mac, &[], Span::new(0, 4), Context::ROOT)?;
120///
121/// let ctx = match out.first() {
122/// Some(Tree::Token { ctx, .. }) => *ctx,
123/// _ => return Err("expected one token".into()),
124/// };
125/// let origin = expander.origin(ctx).ok_or("context not minted by this expander")?;
126/// assert_eq!(origin.macro_name, id);
127/// assert_eq!(origin.call_site, Span::new(0, 4));
128/// assert_eq!(origin.parent, Context::ROOT);
129/// assert_eq!(origin.call_context, Context::ROOT);
130/// # Ok::<(), Box<dyn std::error::Error>>(())
131/// ```
132#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
133#[non_exhaustive]
134pub struct Origin {
135 /// The context the token had in the macro's definition, before this
136 /// expansion marked it.
137 ///
138 /// For a macro defined directly in source this is [`Context::ROOT`]. A name
139 /// resolver falls back to this context to resolve a macro-introduced name
140 /// that the expansion itself does not bind — a call to a global function from
141 /// inside a template, for example — so it resolves where the macro was
142 /// defined rather than where it was called.
143 pub parent: Context,
144 /// The name of the macro whose expansion introduced the token.
145 pub macro_name: Symbol,
146 /// The span of the invocation that triggered the expansion.
147 pub call_site: Span,
148 /// The context of the invocation itself. Following `call_context` outward
149 /// walks the chain of nested expansions, which is what an "in this macro
150 /// invocation" diagnostic backtrace prints.
151 pub call_context: Context,
152}
153
154/// One minted context: the context it marks and the expansion that marked it.
155#[derive(Clone, Copy, Debug)]
156struct ContextData {
157 parent: Context,
158 expansion: usize,
159}
160
161/// One expansion: everything [`Origin`] reports, plus its nesting depth.
162#[derive(Clone, Copy, Debug)]
163struct ExpansionData {
164 macro_name: Symbol,
165 call_site: Span,
166 call_context: Context,
167 depth: u32,
168}
169
170/// The hygiene table an [`Expander`](crate::Expander) owns: every context and
171/// every expansion it has minted, append-only for the expander's lifetime.
172#[derive(Clone, Debug, Default)]
173pub(crate) struct Hygiene {
174 /// `contexts[i]` describes `Context(i + 1)`; the root has no entry.
175 contexts: Vec<ContextData>,
176 expansions: Vec<ExpansionData>,
177}
178
179/// The table sizes at some instant, used to undo a failed expansion.
180#[derive(Clone, Copy, Debug)]
181pub(crate) struct Checkpoint {
182 contexts: usize,
183 expansions: usize,
184}
185
186impl Hygiene {
187 /// Returns the data for a minted context, or `None` for the root or for a
188 /// context this table never minted.
189 #[inline]
190 fn data(&self, ctx: Context) -> Option<&ContextData> {
191 let index = usize::try_from(ctx.0).ok()?.checked_sub(1)?;
192 self.contexts.get(index)
193 }
194
195 /// The expansion depth of the code a token in `ctx` belongs to: `0` for
196 /// source, `n` for code produced `n` expansions deep.
197 #[inline]
198 pub(crate) fn depth(&self, ctx: Context) -> u32 {
199 self.data(ctx)
200 .and_then(|data| self.expansions.get(data.expansion))
201 .map_or(0, |expansion| expansion.depth)
202 }
203
204 /// Reports where a minted context came from.
205 pub(crate) fn origin(&self, ctx: Context) -> Option<Origin> {
206 let data = self.data(ctx)?;
207 let expansion = self.expansions.get(data.expansion)?;
208 Some(Origin {
209 parent: data.parent,
210 macro_name: expansion.macro_name,
211 call_site: expansion.call_site,
212 call_context: expansion.call_context,
213 })
214 }
215
216 /// The number of contexts and expansions recorded, for `Debug` output.
217 #[inline]
218 pub(crate) fn sizes(&self) -> (usize, usize) {
219 (self.contexts.len(), self.expansions.len())
220 }
221
222 /// Records the current table sizes so a failed expansion can be undone.
223 #[inline]
224 pub(crate) fn checkpoint(&self) -> Checkpoint {
225 Checkpoint {
226 contexts: self.contexts.len(),
227 expansions: self.expansions.len(),
228 }
229 }
230
231 /// Discards everything recorded after `checkpoint`.
232 #[inline]
233 pub(crate) fn rollback(&mut self, checkpoint: Checkpoint) {
234 self.contexts.truncate(checkpoint.contexts);
235 self.expansions.truncate(checkpoint.expansions);
236 }
237
238 /// Records a new expansion and returns its index.
239 pub(crate) fn begin(
240 &mut self,
241 macro_name: Symbol,
242 call_site: Span,
243 call_context: Context,
244 depth: u32,
245 ) -> usize {
246 let index = self.expansions.len();
247 self.expansions.push(ExpansionData {
248 macro_name,
249 call_site,
250 call_context,
251 depth,
252 });
253 index
254 }
255
256 /// Mints the context a template token defined in `parent` receives from
257 /// `expansion`, or `None` once all `u32::MAX` contexts are in use.
258 ///
259 /// `cache` holds the `(parent, minted)` pairs already issued by this
260 /// expansion, so every token sharing a definition context shares one minted
261 /// context. A template almost always has a single definition context, so a
262 /// linear scan of the cache beats any map.
263 pub(crate) fn mark(
264 &mut self,
265 parent: Context,
266 expansion: usize,
267 cache: &mut Vec<(Context, Context)>,
268 ) -> Option<Context> {
269 if let Some(&(_, minted)) = cache.iter().find(|(from, _)| *from == parent) {
270 return Some(minted);
271 }
272 let raw = u32::try_from(self.contexts.len()).ok()?.checked_add(1)?;
273 self.contexts.push(ContextData { parent, expansion });
274 let minted = Context(raw);
275 cache.push((parent, minted));
276 Some(minted)
277 }
278}
279
280#[cfg(test)]
281mod tests {
282 #![allow(clippy::unwrap_used)]
283
284 use alloc::string::ToString;
285
286 use super::*;
287
288 fn sym(n: u32) -> Symbol {
289 Symbol::from_u32(n).unwrap()
290 }
291
292 #[test]
293 fn test_root_is_zero_and_default() {
294 assert!(Context::ROOT.is_root());
295 assert_eq!(Context::default(), Context::ROOT);
296 assert_eq!(Context::ROOT.as_u32(), 0);
297 }
298
299 #[test]
300 fn test_display_uses_hash_notation() {
301 assert_eq!(Context(7).to_string(), "#7");
302 }
303
304 #[test]
305 fn test_mark_mints_one_context_per_parent() {
306 let mut table = Hygiene::default();
307 let e = table.begin(sym(1), Span::new(0, 1), Context::ROOT, 1);
308 let mut cache = Vec::new();
309 let a = table.mark(Context::ROOT, e, &mut cache).unwrap();
310 let b = table.mark(Context::ROOT, e, &mut cache).unwrap();
311 assert_eq!(a, b);
312 assert!(!a.is_root());
313 let c = table.mark(a, e, &mut cache).unwrap();
314 assert_ne!(a, c);
315 }
316
317 #[test]
318 fn test_separate_expansions_mint_distinct_contexts() {
319 let mut table = Hygiene::default();
320 let e1 = table.begin(sym(1), Span::new(0, 1), Context::ROOT, 1);
321 let a = table.mark(Context::ROOT, e1, &mut Vec::new()).unwrap();
322 let e2 = table.begin(sym(1), Span::new(5, 6), Context::ROOT, 1);
323 let b = table.mark(Context::ROOT, e2, &mut Vec::new()).unwrap();
324 assert_ne!(a, b);
325 }
326
327 #[test]
328 fn test_origin_reports_expansion_fields() {
329 let mut table = Hygiene::default();
330 let e = table.begin(sym(4), Span::new(3, 9), Context::ROOT, 1);
331 let ctx = table.mark(Context::ROOT, e, &mut Vec::new()).unwrap();
332 let origin = table.origin(ctx).unwrap();
333 assert_eq!(origin.macro_name, sym(4));
334 assert_eq!(origin.call_site, Span::new(3, 9));
335 assert_eq!(origin.parent, Context::ROOT);
336 assert_eq!(origin.call_context, Context::ROOT);
337 }
338
339 #[test]
340 fn test_origin_of_root_and_unknown_is_none() {
341 let table = Hygiene::default();
342 assert!(table.origin(Context::ROOT).is_none());
343 assert!(table.origin(Context(42)).is_none());
344 }
345
346 #[test]
347 fn test_depth_follows_expansion() {
348 let mut table = Hygiene::default();
349 assert_eq!(table.depth(Context::ROOT), 0);
350 let e = table.begin(sym(1), Span::new(0, 1), Context::ROOT, 3);
351 let ctx = table.mark(Context::ROOT, e, &mut Vec::new()).unwrap();
352 assert_eq!(table.depth(ctx), 3);
353 assert_eq!(table.depth(Context(99)), 0);
354 }
355
356 #[test]
357 fn test_rollback_discards_later_records() {
358 let mut table = Hygiene::default();
359 let saved = table.checkpoint();
360 let e = table.begin(sym(1), Span::new(0, 1), Context::ROOT, 1);
361 let ctx = table.mark(Context::ROOT, e, &mut Vec::new()).unwrap();
362 table.rollback(saved);
363 assert!(table.origin(ctx).is_none());
364 assert_eq!(table.checkpoint().contexts, 0);
365 assert_eq!(table.checkpoint().expansions, 0);
366 }
367}