Skip to main content

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}