1 //! A stably addressed token buffer supporting efficient traversal based on a
2 //! cheaply copyable cursor.
3 //!
4 //! *This module is available only 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 ))]
14 use crate::proc_macro as pm;
15 use proc_macro2::{Delimiter, Group, Ident, Literal, Punct, Spacing, Span, TokenStream, TokenTree};
16
17 use std::marker::PhantomData;
18 use std::ptr;
19
20 use crate::Lifetime;
21
22 /// Internal type which is used instead of `TokenTree` to represent a token tree
23 /// within a `TokenBuffer`.
24 enum 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 only if Syn is built with the `"parsing"` feature.*
40 pub 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
47 impl 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.
inner_new(stream: TokenStream, up: *const Entry) -> TokenBuffer50 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 only 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 ))]
new(stream: pm::TokenStream) -> TokenBuffer107 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`.
new2(stream: TokenStream) -> TokenBuffer113 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.
begin(&self) -> Cursor119 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 only if Syn is built with the `"parsing"` feature.*
137 #[derive(Copy, Clone, Eq, PartialEq)]
138 pub 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
149 impl<'a> Cursor<'a> {
150 /// Creates a cursor referencing a static empty TokenStream.
empty() -> Self151 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.
create(mut ptr: *const Entry, scope: *const Entry) -> Self173 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.
entry(self) -> &'a Entry193 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`.
bump(self) -> Cursor<'a>200 unsafe fn bump(self) -> Cursor<'a> {
201 Cursor::create(self.ptr.offset(1), self.scope)
202 }
203
204 /// While the cursor is looking at a `None`-delimited group, move it to look
205 /// at 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.
ignore_none(&mut self)209 fn ignore_none(&mut self) {
210 while 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 } else {
219 break;
220 }
221 }
222 }
223
224 /// Checks whether the cursor is currently pointing at the end of its valid
225 /// scope.
eof(self) -> bool226 pub fn eof(self) -> bool {
227 // We're at eof if we're at the end of our scope.
228 self.ptr == self.scope
229 }
230
231 /// If the cursor is pointing at a `Group` with the given delimiter, returns
232 /// a cursor into that group and one pointing to the next `TokenTree`.
group(mut self, delim: Delimiter) -> Option<(Cursor<'a>, Span, Cursor<'a>)>233 pub fn group(mut self, delim: Delimiter) -> Option<(Cursor<'a>, Span, Cursor<'a>)> {
234 // If we're not trying to enter a none-delimited group, we want to
235 // ignore them. We have to make sure to _not_ ignore them when we want
236 // to enter them, of course. For obvious reasons.
237 if delim != Delimiter::None {
238 self.ignore_none();
239 }
240
241 if let Entry::Group(group, buf) = self.entry() {
242 if group.delimiter() == delim {
243 return Some((buf.begin(), group.span(), unsafe { self.bump() }));
244 }
245 }
246
247 None
248 }
249
250 /// If the cursor is pointing at a `Ident`, returns it along with a cursor
251 /// pointing at the next `TokenTree`.
ident(mut self) -> Option<(Ident, Cursor<'a>)>252 pub fn ident(mut self) -> Option<(Ident, Cursor<'a>)> {
253 self.ignore_none();
254 match self.entry() {
255 Entry::Ident(ident) => Some((ident.clone(), unsafe { self.bump() })),
256 _ => None,
257 }
258 }
259
260 /// If the cursor is pointing at an `Punct`, returns it along with a cursor
261 /// pointing at the next `TokenTree`.
punct(mut self) -> Option<(Punct, Cursor<'a>)>262 pub fn punct(mut self) -> Option<(Punct, Cursor<'a>)> {
263 self.ignore_none();
264 match self.entry() {
265 Entry::Punct(op) if op.as_char() != '\'' => Some((op.clone(), unsafe { self.bump() })),
266 _ => None,
267 }
268 }
269
270 /// If the cursor is pointing at a `Literal`, return it along with a cursor
271 /// pointing at the next `TokenTree`.
literal(mut self) -> Option<(Literal, Cursor<'a>)>272 pub fn literal(mut self) -> Option<(Literal, Cursor<'a>)> {
273 self.ignore_none();
274 match self.entry() {
275 Entry::Literal(lit) => Some((lit.clone(), unsafe { self.bump() })),
276 _ => None,
277 }
278 }
279
280 /// If the cursor is pointing at a `Lifetime`, returns it along with a
281 /// cursor pointing at the next `TokenTree`.
lifetime(mut self) -> Option<(Lifetime, Cursor<'a>)>282 pub fn lifetime(mut self) -> Option<(Lifetime, Cursor<'a>)> {
283 self.ignore_none();
284 match self.entry() {
285 Entry::Punct(op) if op.as_char() == '\'' && op.spacing() == Spacing::Joint => {
286 let next = unsafe { self.bump() };
287 match next.ident() {
288 Some((ident, rest)) => {
289 let lifetime = Lifetime {
290 apostrophe: op.span(),
291 ident,
292 };
293 Some((lifetime, rest))
294 }
295 None => None,
296 }
297 }
298 _ => None,
299 }
300 }
301
302 /// Copies all remaining tokens visible from this cursor into a
303 /// `TokenStream`.
token_stream(self) -> TokenStream304 pub fn token_stream(self) -> TokenStream {
305 let mut tts = Vec::new();
306 let mut cursor = self;
307 while let Some((tt, rest)) = cursor.token_tree() {
308 tts.push(tt);
309 cursor = rest;
310 }
311 tts.into_iter().collect()
312 }
313
314 /// If the cursor is pointing at a `TokenTree`, returns it along with a
315 /// cursor pointing at the next `TokenTree`.
316 ///
317 /// Returns `None` if the cursor has reached the end of its stream.
318 ///
319 /// This method does not treat `None`-delimited groups as transparent, and
320 /// will return a `Group(None, ..)` if the cursor is looking at one.
token_tree(self) -> Option<(TokenTree, Cursor<'a>)>321 pub fn token_tree(self) -> Option<(TokenTree, Cursor<'a>)> {
322 let tree = match self.entry() {
323 Entry::Group(group, _) => group.clone().into(),
324 Entry::Literal(lit) => lit.clone().into(),
325 Entry::Ident(ident) => ident.clone().into(),
326 Entry::Punct(op) => op.clone().into(),
327 Entry::End(..) => {
328 return None;
329 }
330 };
331
332 Some((tree, unsafe { self.bump() }))
333 }
334
335 /// Returns the `Span` of the current token, or `Span::call_site()` if this
336 /// cursor points to eof.
span(self) -> Span337 pub fn span(self) -> Span {
338 match self.entry() {
339 Entry::Group(group, _) => group.span(),
340 Entry::Literal(l) => l.span(),
341 Entry::Ident(t) => t.span(),
342 Entry::Punct(o) => o.span(),
343 Entry::End(..) => Span::call_site(),
344 }
345 }
346
347 /// Skip over the next token without cloning it. Returns `None` if this
348 /// cursor points to eof.
349 ///
350 /// This method treats `'lifetimes` as a single token.
skip(self) -> Option<Cursor<'a>>351 pub(crate) fn skip(self) -> Option<Cursor<'a>> {
352 match self.entry() {
353 Entry::End(..) => None,
354
355 // Treat lifetimes as a single tt for the purposes of 'skip'.
356 Entry::Punct(op) if op.as_char() == '\'' && op.spacing() == Spacing::Joint => {
357 let next = unsafe { self.bump() };
358 match next.entry() {
359 Entry::Ident(_) => Some(unsafe { next.bump() }),
360 _ => Some(next),
361 }
362 }
363 _ => Some(unsafe { self.bump() }),
364 }
365 }
366 }
367
same_scope(a: Cursor, b: Cursor) -> bool368 pub(crate) fn same_scope(a: Cursor, b: Cursor) -> bool {
369 a.scope == b.scope
370 }
371
open_span_of_group(cursor: Cursor) -> Span372 pub(crate) fn open_span_of_group(cursor: Cursor) -> Span {
373 match cursor.entry() {
374 Entry::Group(group, _) => group.span_open(),
375 _ => cursor.span(),
376 }
377 }
378
close_span_of_group(cursor: Cursor) -> Span379 pub(crate) fn close_span_of_group(cursor: Cursor) -> Span {
380 match cursor.entry() {
381 Entry::Group(group, _) => group.span_close(),
382 _ => cursor.span(),
383 }
384 }
385