1//! A stably addressed token buffer supporting efficient traversal based on a
2//! cheaply copyable cursor.
3
4// This module is heavily commented as it contains most of the unsafe code in
5// Syn, and caution should be used when editing it. The public-facing interface
6// is 100% safe but the implementation is fragile internally.
7
8use crate::Lifetime;
9use proc_macro2::extra::DelimSpan;
10use proc_macro2::{Delimiter, Group, Ident, Literal, Punct, Spacing, Span, TokenStream, TokenTree};
11use std::cmp::Ordering;
12use std::marker::PhantomData;
13
14/// Internal type which is used instead of `TokenTree` to represent a token tree
15/// within a `TokenBuffer`.
16enum Entry {
17 // Mimicking types from proc-macro.
18 // Group entries contain the offset to the matching End entry.
19 Group(Group, usize),
20 Ident(Ident),
21 Punct(Punct),
22 Literal(Literal),
23 // End entries contain the offset (negative) to the start of the buffer, and
24 // offset (negative) to the matching Group entry.
25 End(isize, isize),
26}
27
28/// A buffer that can be efficiently traversed multiple times, unlike
29/// `TokenStream` which requires a deep copy in order to traverse more than
30/// once.
31pub struct TokenBuffer {
32 // NOTE: Do not implement clone on this - while the current design could be
33 // cloned, other designs which could be desirable may not be cloneable.
34 entries: Box<[Entry]>,
35}
36
37impl TokenBuffer {
38 fn recursive_new(entries: &mut Vec<Entry>, stream: TokenStream) {
39 for tt in stream {
40 match tt {
41 TokenTree::Ident(ident) => entries.push(Entry::Ident(ident)),
42 TokenTree::Punct(punct) => entries.push(Entry::Punct(punct)),
43 TokenTree::Literal(literal) => entries.push(Entry::Literal(literal)),
44 TokenTree::Group(group) => {
45 let group_start_index = entries.len();
46 entries.push(Entry::End(0, 0)); // we replace this below
47 Self::recursive_new(entries, group.stream());
48 let group_end_index = entries.len();
49 let group_offset = group_end_index - group_start_index;
50 entries.push(Entry::End(
51 -(group_end_index as isize),
52 -(group_offset as isize),
53 ));
54 entries[group_start_index] = Entry::Group(group, group_offset);
55 }
56 }
57 }
58 }
59
60 /// Creates a `TokenBuffer` containing all the tokens from the input
61 /// `proc_macro::TokenStream`.
62 #[cfg(feature = "proc-macro")]
63 #[cfg_attr(docsrs, doc(cfg(feature = "proc-macro")))]
64 pub fn new(stream: proc_macro::TokenStream) -> Self {
65 Self::new2(stream.into())
66 }
67
68 /// Creates a `TokenBuffer` containing all the tokens from the input
69 /// `proc_macro2::TokenStream`.
70 pub fn new2(stream: TokenStream) -> Self {
71 let mut entries = Vec::new();
72 Self::recursive_new(&mut entries, stream);
73 entries.push(Entry::End(-(entries.len() as isize), 0));
74 Self {
75 entries: entries.into_boxed_slice(),
76 }
77 }
78
79 /// Creates a cursor referencing the first token in the buffer and able to
80 /// traverse until the end of the buffer.
81 pub fn begin(&self) -> Cursor {
82 let ptr = self.entries.as_ptr();
83 unsafe { Cursor::create(ptr, ptr.add(self.entries.len() - 1)) }
84 }
85}
86
87/// A cheaply copyable cursor into a `TokenBuffer`.
88///
89/// This cursor holds a shared reference into the immutable data which is used
90/// internally to represent a `TokenStream`, and can be efficiently manipulated
91/// and copied around.
92///
93/// An empty `Cursor` can be created directly, or one may create a `TokenBuffer`
94/// object and get a cursor to its first token with `begin()`.
95pub struct Cursor<'a> {
96 // The current entry which the `Cursor` is pointing at.
97 ptr: *const Entry,
98 // This is the only `Entry::End` object which this cursor is allowed to
99 // point at. All other `End` objects are skipped over in `Cursor::create`.
100 scope: *const Entry,
101 // Cursor is covariant in 'a. This field ensures that our pointers are still
102 // valid.
103 marker: PhantomData<&'a Entry>,
104}
105
106impl<'a> Cursor<'a> {
107 /// Creates a cursor referencing a static empty TokenStream.
108 pub fn empty() -> Self {
109 // It's safe in this situation for us to put an `Entry` object in global
110 // storage, despite it not actually being safe to send across threads
111 // (`Ident` is a reference into a thread-local table). This is because
112 // this entry never includes a `Ident` object.
113 //
114 // This wrapper struct allows us to break the rules and put a `Sync`
115 // object in global storage.
116 struct UnsafeSyncEntry(Entry);
117 unsafe impl Sync for UnsafeSyncEntry {}
118 static EMPTY_ENTRY: UnsafeSyncEntry = UnsafeSyncEntry(Entry::End(0, 0));
119
120 Cursor {
121 ptr: &EMPTY_ENTRY.0,
122 scope: &EMPTY_ENTRY.0,
123 marker: PhantomData,
124 }
125 }
126
127 /// This create method intelligently exits non-explicitly-entered
128 /// `None`-delimited scopes when the cursor reaches the end of them,
129 /// allowing for them to be treated transparently.
130 unsafe fn create(mut ptr: *const Entry, scope: *const Entry) -> Self {
131 // NOTE: If we're looking at a `End`, we want to advance the cursor
132 // past it, unless `ptr == scope`, which means that we're at the edge of
133 // our cursor's scope. We should only have `ptr != scope` at the exit
134 // from None-delimited groups entered with `ignore_none`.
135 while let Entry::End(..) = unsafe { &*ptr } {
136 if ptr == scope {
137 break;
138 }
139 ptr = unsafe { ptr.add(1) };
140 }
141
142 Cursor {
143 ptr,
144 scope,
145 marker: PhantomData,
146 }
147 }
148
149 /// Get the current entry.
150 fn entry(self) -> &'a Entry {
151 unsafe { &*self.ptr }
152 }
153
154 /// Bump the cursor to point at the next token after the current one. This
155 /// is undefined behavior if the cursor is currently looking at an
156 /// `Entry::End`.
157 ///
158 /// If the cursor is looking at an `Entry::Group`, the bumped cursor will
159 /// point at the first token in the group (with the same scope end).
160 unsafe fn bump_ignore_group(self) -> Cursor<'a> {
161 unsafe { Cursor::create(self.ptr.offset(1), self.scope) }
162 }
163
164 /// While the cursor is looking at a `None`-delimited group, move it to look
165 /// at the first token inside instead. If the group is empty, this will move
166 /// the cursor past the `None`-delimited group.
167 ///
168 /// WARNING: This mutates its argument.
169 fn ignore_none(&mut self) {
170 while let Entry::Group(group, _) = self.entry() {
171 if group.delimiter() == Delimiter::None {
172 unsafe { *self = self.bump_ignore_group() };
173 } else {
174 break;
175 }
176 }
177 }
178
179 /// Checks whether the cursor is currently pointing at the end of its valid
180 /// scope.
181 pub fn eof(self) -> bool {
182 // We're at eof if we're at the end of our scope.
183 self.ptr == self.scope
184 }
185
186 /// If the cursor is pointing at a `Ident`, returns it along with a cursor
187 /// pointing at the next `TokenTree`.
188 pub fn ident(mut self) -> Option<(Ident, Cursor<'a>)> {
189 self.ignore_none();
190 match self.entry() {
191 Entry::Ident(ident) => Some((ident.clone(), unsafe { self.bump_ignore_group() })),
192 _ => None,
193 }
194 }
195
196 /// If the cursor is pointing at a `Punct`, returns it along with a cursor
197 /// pointing at the next `TokenTree`.
198 pub fn punct(mut self) -> Option<(Punct, Cursor<'a>)> {
199 self.ignore_none();
200 match self.entry() {
201 Entry::Punct(punct) if punct.as_char() != '\'' => {
202 Some((punct.clone(), unsafe { self.bump_ignore_group() }))
203 }
204 _ => None,
205 }
206 }
207
208 /// If the cursor is pointing at a `Literal`, return it along with a cursor
209 /// pointing at the next `TokenTree`.
210 pub fn literal(mut self) -> Option<(Literal, Cursor<'a>)> {
211 self.ignore_none();
212 match self.entry() {
213 Entry::Literal(literal) => Some((literal.clone(), unsafe { self.bump_ignore_group() })),
214 _ => None,
215 }
216 }
217
218 /// If the cursor is pointing at a `Lifetime`, returns it along with a
219 /// cursor pointing at the next `TokenTree`.
220 pub fn lifetime(mut self) -> Option<(Lifetime, Cursor<'a>)> {
221 self.ignore_none();
222 match self.entry() {
223 Entry::Punct(punct) if punct.as_char() == '\'' && punct.spacing() == Spacing::Joint => {
224 let next = unsafe { self.bump_ignore_group() };
225 let (ident, rest) = next.ident()?;
226 let lifetime = Lifetime {
227 apostrophe: punct.span(),
228 ident,
229 };
230 Some((lifetime, rest))
231 }
232 _ => None,
233 }
234 }
235
236 /// If the cursor is pointing at a `Group` with the given delimiter, returns
237 /// a cursor into that group and one pointing to the next `TokenTree`.
238 pub fn group(mut self, delim: Delimiter) -> Option<(Cursor<'a>, DelimSpan, Cursor<'a>)> {
239 // If we're not trying to enter a none-delimited group, we want to
240 // ignore them. We have to make sure to _not_ ignore them when we want
241 // to enter them, of course. For obvious reasons.
242 if delim != Delimiter::None {
243 self.ignore_none();
244 }
245
246 if let Entry::Group(group, end_offset) = self.entry() {
247 if group.delimiter() == delim {
248 let span = group.delim_span();
249 let end_of_group = unsafe { self.ptr.add(*end_offset) };
250 let inside_of_group = unsafe { Cursor::create(self.ptr.add(1), end_of_group) };
251 let after_group = unsafe { Cursor::create(end_of_group, self.scope) };
252 return Some((inside_of_group, span, after_group));
253 }
254 }
255
256 None
257 }
258
259 /// If the cursor is pointing at a `Group`, returns a cursor into the group
260 /// and one pointing to the next `TokenTree`.
261 pub fn any_group(self) -> Option<(Cursor<'a>, Delimiter, DelimSpan, Cursor<'a>)> {
262 if let Entry::Group(group, end_offset) = self.entry() {
263 let delimiter = group.delimiter();
264 let span = group.delim_span();
265 let end_of_group = unsafe { self.ptr.add(*end_offset) };
266 let inside_of_group = unsafe { Cursor::create(self.ptr.add(1), end_of_group) };
267 let after_group = unsafe { Cursor::create(end_of_group, self.scope) };
268 return Some((inside_of_group, delimiter, span, after_group));
269 }
270
271 None
272 }
273
274 pub(crate) fn any_group_token(self) -> Option<(Group, Cursor<'a>)> {
275 if let Entry::Group(group, end_offset) = self.entry() {
276 let end_of_group = unsafe { self.ptr.add(*end_offset) };
277 let after_group = unsafe { Cursor::create(end_of_group, self.scope) };
278 return Some((group.clone(), after_group));
279 }
280
281 None
282 }
283
284 /// Copies all remaining tokens visible from this cursor into a
285 /// `TokenStream`.
286 pub fn token_stream(self) -> TokenStream {
287 let mut tts = Vec::new();
288 let mut cursor = self;
289 while let Some((tt, rest)) = cursor.token_tree() {
290 tts.push(tt);
291 cursor = rest;
292 }
293 tts.into_iter().collect()
294 }
295
296 /// If the cursor is pointing at a `TokenTree`, returns it along with a
297 /// cursor pointing at the next `TokenTree`.
298 ///
299 /// Returns `None` if the cursor has reached the end of its stream.
300 ///
301 /// This method does not treat `None`-delimited groups as transparent, and
302 /// will return a `Group(None, ..)` if the cursor is looking at one.
303 pub fn token_tree(self) -> Option<(TokenTree, Cursor<'a>)> {
304 let (tree, len) = match self.entry() {
305 Entry::Group(group, end_offset) => (group.clone().into(), *end_offset),
306 Entry::Literal(literal) => (literal.clone().into(), 1),
307 Entry::Ident(ident) => (ident.clone().into(), 1),
308 Entry::Punct(punct) => (punct.clone().into(), 1),
309 Entry::End(..) => return None,
310 };
311
312 let rest = unsafe { Cursor::create(self.ptr.add(len), self.scope) };
313 Some((tree, rest))
314 }
315
316 /// Returns the `Span` of the current token, or `Span::call_site()` if this
317 /// cursor points to eof.
318 pub fn span(mut self) -> Span {
319 match self.entry() {
320 Entry::Group(group, _) => group.span(),
321 Entry::Literal(literal) => literal.span(),
322 Entry::Ident(ident) => ident.span(),
323 Entry::Punct(punct) => punct.span(),
324 Entry::End(_, offset) => {
325 self.ptr = unsafe { self.ptr.offset(*offset) };
326 if let Entry::Group(group, _) = self.entry() {
327 group.span_close()
328 } else {
329 Span::call_site()
330 }
331 }
332 }
333 }
334
335 /// Returns the `Span` of the token immediately prior to the position of
336 /// this cursor, or of the current token if there is no previous one.
337 #[cfg(any(feature = "full", feature = "derive"))]
338 pub(crate) fn prev_span(mut self) -> Span {
339 if start_of_buffer(self) < self.ptr {
340 self.ptr = unsafe { self.ptr.offset(-1) };
341 }
342 self.span()
343 }
344
345 /// Skip over the next token that is not a None-delimited group, without
346 /// cloning it. Returns `None` if this cursor points to eof.
347 ///
348 /// This method treats `'lifetimes` as a single token.
349 pub(crate) fn skip(mut self) -> Option<Cursor<'a>> {
350 self.ignore_none();
351
352 let len = match self.entry() {
353 Entry::End(..) => return None,
354
355 // Treat lifetimes as a single tt for the purposes of 'skip'.
356 Entry::Punct(punct) if punct.as_char() == '\'' && punct.spacing() == Spacing::Joint => {
357 match unsafe { &*self.ptr.add(1) } {
358 Entry::Ident(_) => 2,
359 _ => 1,
360 }
361 }
362
363 Entry::Group(_, end_offset) => *end_offset,
364 _ => 1,
365 };
366
367 Some(unsafe { Cursor::create(self.ptr.add(len), self.scope) })
368 }
369
370 pub(crate) fn scope_delimiter(self) -> Delimiter {
371 match unsafe { &*self.scope } {
372 Entry::End(_, offset) => match unsafe { &*self.scope.offset(*offset) } {
373 Entry::Group(group, _) => group.delimiter(),
374 _ => Delimiter::None,
375 },
376 _ => unreachable!(),
377 }
378 }
379}
380
381impl<'a> Copy for Cursor<'a> {}
382
383impl<'a> Clone for Cursor<'a> {
384 fn clone(&self) -> Self {
385 *self
386 }
387}
388
389impl<'a> Eq for Cursor<'a> {}
390
391impl<'a> PartialEq for Cursor<'a> {
392 fn eq(&self, other: &Self) -> bool {
393 self.ptr == other.ptr
394 }
395}
396
397impl<'a> PartialOrd for Cursor<'a> {
398 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
399 if same_buffer(*self, *other) {
400 Some(cmp_assuming_same_buffer(*self, *other))
401 } else {
402 None
403 }
404 }
405}
406
407pub(crate) fn same_scope(a: Cursor, b: Cursor) -> bool {
408 a.scope == b.scope
409}
410
411pub(crate) fn same_buffer(a: Cursor, b: Cursor) -> bool {
412 start_of_buffer(cursor:a) == start_of_buffer(cursor:b)
413}
414
415fn start_of_buffer(cursor: Cursor) -> *const Entry {
416 unsafe {
417 match &*cursor.scope {
418 Entry::End(offset: &isize, _) => cursor.scope.offset(*offset),
419 _ => unreachable!(),
420 }
421 }
422}
423
424pub(crate) fn cmp_assuming_same_buffer(a: Cursor, b: Cursor) -> Ordering {
425 a.ptr.cmp(&b.ptr)
426}
427
428pub(crate) fn open_span_of_group(cursor: Cursor) -> Span {
429 match cursor.entry() {
430 Entry::Group(group: &Group, _) => group.span_open(),
431 _ => cursor.span(),
432 }
433}
434