syn/
buffer.rs

1//! A stably addressed token buffer supporting efficient traversal based on a
2//! cheaply copyable cursor.
3//!
4//! *This module is available if Syn is built with the `"parsing"` feature.*
5
6// This module is heavily commented as it contains most of the unsafe code in
7// Syn, and caution should be used when editing it. The public-facing interface
8// is 100% safe but the implementation is fragile internally.
9
10#[cfg(all(
11    not(all(target_arch = "wasm32", any(target_os = "unknown", target_os = "wasi"))),
12    feature = "proc-macro"
13))]
14use crate::proc_macro as pm;
15use proc_macro2::{Delimiter, Group, Ident, Literal, Punct, Spacing, Span, TokenStream, TokenTree};
16
17use std::marker::PhantomData;
18use std::ptr;
19
20use crate::Lifetime;
21
22/// Internal type which is used instead of `TokenTree` to represent a token tree
23/// within a `TokenBuffer`.
24enum Entry {
25    // Mimicking types from proc-macro.
26    Group(Group, TokenBuffer),
27    Ident(Ident),
28    Punct(Punct),
29    Literal(Literal),
30    // End entries contain a raw pointer to the entry from the containing
31    // token tree, or null if this is the outermost level.
32    End(*const Entry),
33}
34
35/// A buffer that can be efficiently traversed multiple times, unlike
36/// `TokenStream` which requires a deep copy in order to traverse more than
37/// once.
38///
39/// *This type is available if Syn is built with the `"parsing"` feature.*
40pub struct TokenBuffer {
41    // NOTE: Do not derive clone on this - there are raw pointers inside which
42    // will be messed up. Moving the `TokenBuffer` itself is safe as the actual
43    // backing slices won't be moved.
44    data: Box<[Entry]>,
45}
46
47impl TokenBuffer {
48    // NOTE: DO NOT MUTATE THE `Vec` RETURNED FROM THIS FUNCTION ONCE IT
49    // RETURNS, THE ADDRESS OF ITS BACKING MEMORY MUST REMAIN STABLE.
50    fn inner_new(stream: TokenStream, up: *const Entry) -> TokenBuffer {
51        // Build up the entries list, recording the locations of any Groups
52        // in the list to be processed later.
53        let mut entries = Vec::new();
54        let mut seqs = Vec::new();
55        for tt in stream {
56            match tt {
57                TokenTree::Ident(sym) => {
58                    entries.push(Entry::Ident(sym));
59                }
60                TokenTree::Punct(op) => {
61                    entries.push(Entry::Punct(op));
62                }
63                TokenTree::Literal(l) => {
64                    entries.push(Entry::Literal(l));
65                }
66                TokenTree::Group(g) => {
67                    // Record the index of the interesting entry, and store an
68                    // `End(null)` there temporarially.
69                    seqs.push((entries.len(), g));
70                    entries.push(Entry::End(ptr::null()));
71                }
72            }
73        }
74        // Add an `End` entry to the end with a reference to the enclosing token
75        // stream which was passed in.
76        entries.push(Entry::End(up));
77
78        // NOTE: This is done to ensure that we don't accidentally modify the
79        // length of the backing buffer. The backing buffer must remain at a
80        // constant address after this point, as we are going to store a raw
81        // pointer into it.
82        let mut entries = entries.into_boxed_slice();
83        for (idx, group) in seqs {
84            // We know that this index refers to one of the temporary
85            // `End(null)` entries, and we know that the last entry is
86            // `End(up)`, so the next index is also valid.
87            let seq_up = &entries[idx + 1] as *const Entry;
88
89            // The end entry stored at the end of this Entry::Group should
90            // point to the Entry which follows the Group in the list.
91            let inner = Self::inner_new(group.stream(), seq_up);
92            entries[idx] = Entry::Group(group, inner);
93        }
94
95        TokenBuffer { data: entries }
96    }
97
98    /// Creates a `TokenBuffer` containing all the tokens from the input
99    /// `TokenStream`.
100    ///
101    /// *This method is available if Syn is built with both the `"parsing"` and
102    /// `"proc-macro"` features.*
103    #[cfg(all(
104        not(all(target_arch = "wasm32", any(target_os = "unknown", target_os = "wasi"))),
105        feature = "proc-macro"
106    ))]
107    pub fn new(stream: pm::TokenStream) -> TokenBuffer {
108        Self::new2(stream.into())
109    }
110
111    /// Creates a `TokenBuffer` containing all the tokens from the input
112    /// `TokenStream`.
113    pub fn new2(stream: TokenStream) -> TokenBuffer {
114        Self::inner_new(stream, ptr::null())
115    }
116
117    /// Creates a cursor referencing the first token in the buffer and able to
118    /// traverse until the end of the buffer.
119    pub fn begin(&self) -> Cursor {
120        unsafe { Cursor::create(&self.data[0], &self.data[self.data.len() - 1]) }
121    }
122}
123
124/// A cheaply copyable cursor into a `TokenBuffer`.
125///
126/// This cursor holds a shared reference into the immutable data which is used
127/// internally to represent a `TokenStream`, and can be efficiently manipulated
128/// and copied around.
129///
130/// An empty `Cursor` can be created directly, or one may create a `TokenBuffer`
131/// object and get a cursor to its first token with `begin()`.
132///
133/// Two cursors are equal if they have the same location in the same input
134/// stream, and have the same scope.
135///
136/// *This type is available if Syn is built with the `"parsing"` feature.*
137#[derive(Copy, Clone, Eq, PartialEq)]
138pub struct Cursor<'a> {
139    // The current entry which the `Cursor` is pointing at.
140    ptr: *const Entry,
141    // This is the only `Entry::End(..)` object which this cursor is allowed to
142    // point at. All other `End` objects are skipped over in `Cursor::create`.
143    scope: *const Entry,
144    // Cursor is covariant in 'a. This field ensures that our pointers are still
145    // valid.
146    marker: PhantomData<&'a Entry>,
147}
148
149impl<'a> Cursor<'a> {
150    /// Creates a cursor referencing a static empty TokenStream.
151    pub fn empty() -> Self {
152        // It's safe in this situation for us to put an `Entry` object in global
153        // storage, despite it not actually being safe to send across threads
154        // (`Ident` is a reference into a thread-local table). This is because
155        // this entry never includes a `Ident` object.
156        //
157        // This wrapper struct allows us to break the rules and put a `Sync`
158        // object in global storage.
159        struct UnsafeSyncEntry(Entry);
160        unsafe impl Sync for UnsafeSyncEntry {}
161        static EMPTY_ENTRY: UnsafeSyncEntry = UnsafeSyncEntry(Entry::End(0 as *const Entry));
162
163        Cursor {
164            ptr: &EMPTY_ENTRY.0,
165            scope: &EMPTY_ENTRY.0,
166            marker: PhantomData,
167        }
168    }
169
170    /// This create method intelligently exits non-explicitly-entered
171    /// `None`-delimited scopes when the cursor reaches the end of them,
172    /// allowing for them to be treated transparently.
173    unsafe fn create(mut ptr: *const Entry, scope: *const Entry) -> Self {
174        // NOTE: If we're looking at a `End(..)`, we want to advance the cursor
175        // past it, unless `ptr == scope`, which means that we're at the edge of
176        // our cursor's scope. We should only have `ptr != scope` at the exit
177        // from None-delimited groups entered with `ignore_none`.
178        while let Entry::End(exit) = *ptr {
179            if ptr == scope {
180                break;
181            }
182            ptr = exit;
183        }
184
185        Cursor {
186            ptr,
187            scope,
188            marker: PhantomData,
189        }
190    }
191
192    /// Get the current entry.
193    fn entry(self) -> &'a Entry {
194        unsafe { &*self.ptr }
195    }
196
197    /// Bump the cursor to point at the next token after the current one. This
198    /// is undefined behavior if the cursor is currently looking at an
199    /// `Entry::End`.
200    unsafe fn bump(self) -> Cursor<'a> {
201        Cursor::create(self.ptr.offset(1), self.scope)
202    }
203
204    /// If the cursor is looking at a `None`-delimited group, move it to look at
205    /// the first token inside instead. If the group is empty, this will move
206    /// the cursor past the `None`-delimited group.
207    ///
208    /// WARNING: This mutates its argument.
209    fn ignore_none(&mut self) {
210        if let Entry::Group(group, buf) = self.entry() {
211            if group.delimiter() == Delimiter::None {
212                // NOTE: We call `Cursor::create` here to make sure that
213                // situations where we should immediately exit the span after
214                // entering it are handled correctly.
215                unsafe {
216                    *self = Cursor::create(&buf.data[0], self.scope);
217                }
218            }
219        }
220    }
221
222    /// Checks whether the cursor is currently pointing at the end of its valid
223    /// scope.
224    pub fn eof(self) -> bool {
225        // We're at eof if we're at the end of our scope.
226        self.ptr == self.scope
227    }
228
229    /// If the cursor is pointing at a `Group` with the given delimiter, returns
230    /// a cursor into that group and one pointing to the next `TokenTree`.
231    pub fn group(mut self, delim: Delimiter) -> Option<(Cursor<'a>, Span, Cursor<'a>)> {
232        // If we're not trying to enter a none-delimited group, we want to
233        // ignore them. We have to make sure to _not_ ignore them when we want
234        // to enter them, of course. For obvious reasons.
235        if delim != Delimiter::None {
236            self.ignore_none();
237        }
238
239        if let Entry::Group(group, buf) = self.entry() {
240            if group.delimiter() == delim {
241                return Some((buf.begin(), group.span(), unsafe { self.bump() }));
242            }
243        }
244
245        None
246    }
247
248    /// If the cursor is pointing at a `Ident`, returns it along with a cursor
249    /// pointing at the next `TokenTree`.
250    pub fn ident(mut self) -> Option<(Ident, Cursor<'a>)> {
251        self.ignore_none();
252        match self.entry() {
253            Entry::Ident(ident) => Some((ident.clone(), unsafe { self.bump() })),
254            _ => None,
255        }
256    }
257
258    /// If the cursor is pointing at an `Punct`, returns it along with a cursor
259    /// pointing at the next `TokenTree`.
260    pub fn punct(mut self) -> Option<(Punct, Cursor<'a>)> {
261        self.ignore_none();
262        match self.entry() {
263            Entry::Punct(op) if op.as_char() != '\'' => Some((op.clone(), unsafe { self.bump() })),
264            _ => None,
265        }
266    }
267
268    /// If the cursor is pointing at a `Literal`, return it along with a cursor
269    /// pointing at the next `TokenTree`.
270    pub fn literal(mut self) -> Option<(Literal, Cursor<'a>)> {
271        self.ignore_none();
272        match self.entry() {
273            Entry::Literal(lit) => Some((lit.clone(), unsafe { self.bump() })),
274            _ => None,
275        }
276    }
277
278    /// If the cursor is pointing at a `Lifetime`, returns it along with a
279    /// cursor pointing at the next `TokenTree`.
280    pub fn lifetime(mut self) -> Option<(Lifetime, Cursor<'a>)> {
281        self.ignore_none();
282        match self.entry() {
283            Entry::Punct(op) if op.as_char() == '\'' && op.spacing() == Spacing::Joint => {
284                let next = unsafe { self.bump() };
285                match next.ident() {
286                    Some((ident, rest)) => {
287                        let lifetime = Lifetime {
288                            apostrophe: op.span(),
289                            ident,
290                        };
291                        Some((lifetime, rest))
292                    }
293                    None => None,
294                }
295            }
296            _ => None,
297        }
298    }
299
300    /// Copies all remaining tokens visible from this cursor into a
301    /// `TokenStream`.
302    pub fn token_stream(self) -> TokenStream {
303        let mut tts = Vec::new();
304        let mut cursor = self;
305        while let Some((tt, rest)) = cursor.token_tree() {
306            tts.push(tt);
307            cursor = rest;
308        }
309        tts.into_iter().collect()
310    }
311
312    /// If the cursor is pointing at a `TokenTree`, returns it along with a
313    /// cursor pointing at the next `TokenTree`.
314    ///
315    /// Returns `None` if the cursor has reached the end of its stream.
316    ///
317    /// This method does not treat `None`-delimited groups as transparent, and
318    /// will return a `Group(None, ..)` if the cursor is looking at one.
319    pub fn token_tree(self) -> Option<(TokenTree, Cursor<'a>)> {
320        let tree = match self.entry() {
321            Entry::Group(group, _) => group.clone().into(),
322            Entry::Literal(lit) => lit.clone().into(),
323            Entry::Ident(ident) => ident.clone().into(),
324            Entry::Punct(op) => op.clone().into(),
325            Entry::End(..) => {
326                return None;
327            }
328        };
329
330        Some((tree, unsafe { self.bump() }))
331    }
332
333    /// Returns the `Span` of the current token, or `Span::call_site()` if this
334    /// cursor points to eof.
335    pub fn span(self) -> Span {
336        match self.entry() {
337            Entry::Group(group, _) => group.span(),
338            Entry::Literal(l) => l.span(),
339            Entry::Ident(t) => t.span(),
340            Entry::Punct(o) => o.span(),
341            Entry::End(..) => Span::call_site(),
342        }
343    }
344}
345
346pub(crate) fn same_scope(a: Cursor, b: Cursor) -> bool {
347    a.scope == b.scope
348}
349
350pub(crate) fn open_span_of_group(cursor: Cursor) -> Span {
351    match cursor.entry() {
352        Entry::Group(group, _) => group.span_open(),
353        _ => cursor.span(),
354    }
355}
356
357pub(crate) fn close_span_of_group(cursor: Cursor) -> Span {
358    match cursor.entry() {
359        Entry::Group(group, _) => group.span_close(),
360        _ => cursor.span(),
361    }
362}