1 //! A stably addressed token buffer supporting efficient traversal based on a
2 //! cheaply copyable cursor.
4 //! *This module is available only if Syn is built with the `"parsing"` feature.*
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.
11 not(all(target_arch
= "wasm32", any(target_os
= "unknown", target_os
= "wasi"))),
12 feature
= "proc-macro"
14 use crate::proc_macro
as pm
;
16 use proc_macro2
::{Delimiter, Group, Ident, Literal, Punct, Spacing, Span, TokenStream, TokenTree}
;
17 use std
::cmp
::Ordering
;
18 use std
::marker
::PhantomData
;
20 /// Internal type which is used instead of `TokenTree` to represent a token tree
21 /// within a `TokenBuffer`.
23 // Mimicking types from proc-macro.
24 // Group entries contain the offset to the matching End entry.
29 // End entries contain the offset (negative) to the start of the buffer.
33 /// A buffer that can be efficiently traversed multiple times, unlike
34 /// `TokenStream` which requires a deep copy in order to traverse more than
37 /// *This type is available only if Syn is built with the `"parsing"` feature.*
38 pub struct TokenBuffer
{
39 // NOTE: Do not implement clone on this - while the current design could be
40 // cloned, other designs which could be desirable may not be cloneable.
41 entries
: Box
<[Entry
]>,
45 fn recursive_new(entries
: &mut Vec
<Entry
>, stream
: TokenStream
) {
48 TokenTree
::Ident(ident
) => entries
.push(Entry
::Ident(ident
)),
49 TokenTree
::Punct(punct
) => entries
.push(Entry
::Punct(punct
)),
50 TokenTree
::Literal(literal
) => entries
.push(Entry
::Literal(literal
)),
51 TokenTree
::Group(group
) => {
52 let group_start_index
= entries
.len();
53 entries
.push(Entry
::End(0)); // we replace this below
54 Self::recursive_new(entries
, group
.stream());
55 let group_end_index
= entries
.len();
56 entries
.push(Entry
::End(-(group_end_index
as isize)));
57 let group_end_offset
= group_end_index
- group_start_index
;
58 entries
[group_start_index
] = Entry
::Group(group
, group_end_offset
);
64 /// Creates a `TokenBuffer` containing all the tokens from the input
65 /// `proc_macro::TokenStream`.
67 /// *This method is available only if Syn is built with both the `"parsing"` and
68 /// `"proc-macro"` features.*
70 not(all(target_arch
= "wasm32", any(target_os
= "unknown", target_os
= "wasi"))),
71 feature
= "proc-macro"
73 pub fn new(stream
: pm
::TokenStream
) -> Self {
74 Self::new2(stream
.into())
77 /// Creates a `TokenBuffer` containing all the tokens from the input
78 /// `proc_macro2::TokenStream`.
79 pub fn new2(stream
: TokenStream
) -> Self {
80 let mut entries
= Vec
::new();
81 Self::recursive_new(&mut entries
, stream
);
82 entries
.push(Entry
::End(-(entries
.len() as isize)));
84 entries
: entries
.into_boxed_slice(),
88 /// Creates a cursor referencing the first token in the buffer and able to
89 /// traverse until the end of the buffer.
90 pub fn begin(&self) -> Cursor
{
91 let ptr
= self.entries
.as_ptr();
92 unsafe { Cursor::create(ptr, ptr.add(self.entries.len() - 1)) }
96 /// A cheaply copyable cursor into a `TokenBuffer`.
98 /// This cursor holds a shared reference into the immutable data which is used
99 /// internally to represent a `TokenStream`, and can be efficiently manipulated
100 /// and copied around.
102 /// An empty `Cursor` can be created directly, or one may create a `TokenBuffer`
103 /// object and get a cursor to its first token with `begin()`.
105 /// Two cursors are equal if they have the same location in the same input
106 /// stream, and have the same scope.
108 /// *This type is available only if Syn is built with the `"parsing"` feature.*
109 pub struct Cursor
<'a
> {
110 // The current entry which the `Cursor` is pointing at.
112 // This is the only `Entry::End` object which this cursor is allowed to
113 // point at. All other `End` objects are skipped over in `Cursor::create`.
115 // Cursor is covariant in 'a. This field ensures that our pointers are still
117 marker
: PhantomData
<&'a Entry
>,
120 impl<'a
> Cursor
<'a
> {
121 /// Creates a cursor referencing a static empty TokenStream.
122 pub fn empty() -> Self {
123 // It's safe in this situation for us to put an `Entry` object in global
124 // storage, despite it not actually being safe to send across threads
125 // (`Ident` is a reference into a thread-local table). This is because
126 // this entry never includes a `Ident` object.
128 // This wrapper struct allows us to break the rules and put a `Sync`
129 // object in global storage.
130 struct UnsafeSyncEntry(Entry
);
131 unsafe impl Sync
for UnsafeSyncEntry {}
132 static EMPTY_ENTRY
: UnsafeSyncEntry
= UnsafeSyncEntry(Entry
::End(0));
136 scope
: &EMPTY_ENTRY
.0,
141 /// This create method intelligently exits non-explicitly-entered
142 /// `None`-delimited scopes when the cursor reaches the end of them,
143 /// allowing for them to be treated transparently.
144 unsafe fn create(mut ptr
: *const Entry
, scope
: *const Entry
) -> Self {
145 // NOTE: If we're looking at a `End`, we want to advance the cursor
146 // past it, unless `ptr == scope`, which means that we're at the edge of
147 // our cursor's scope. We should only have `ptr != scope` at the exit
148 // from None-delimited groups entered with `ignore_none`.
149 while let Entry
::End(_
) = *ptr
{
163 /// Get the current entry.
164 fn entry(self) -> &'a Entry
{
165 unsafe { &*self.ptr }
168 /// Bump the cursor to point at the next token after the current one. This
169 /// is undefined behavior if the cursor is currently looking at an
172 /// If the cursor is looking at an `Entry::Group`, the bumped cursor will
173 /// point at the first token in the group (with the same scope end).
174 unsafe fn bump_ignore_group(self) -> Cursor
<'a
> {
175 Cursor
::create(self.ptr
.offset(1), self.scope
)
178 /// While the cursor is looking at a `None`-delimited group, move it to look
179 /// at the first token inside instead. If the group is empty, this will move
180 /// the cursor past the `None`-delimited group.
182 /// WARNING: This mutates its argument.
183 fn ignore_none(&mut self) {
184 while let Entry
::Group(group
, _
) = self.entry() {
185 if group
.delimiter() == Delimiter
::None
{
186 unsafe { *self = self.bump_ignore_group() }
;
193 /// Checks whether the cursor is currently pointing at the end of its valid
195 pub fn eof(self) -> bool
{
196 // We're at eof if we're at the end of our scope.
197 self.ptr
== self.scope
200 /// If the cursor is pointing at a `Group` with the given delimiter, returns
201 /// a cursor into that group and one pointing to the next `TokenTree`.
202 pub fn group(mut self, delim
: Delimiter
) -> Option
<(Cursor
<'a
>, Span
, Cursor
<'a
>)> {
203 // If we're not trying to enter a none-delimited group, we want to
204 // ignore them. We have to make sure to _not_ ignore them when we want
205 // to enter them, of course. For obvious reasons.
206 if delim
!= Delimiter
::None
{
210 if let Entry
::Group(group
, end_offset
) = self.entry() {
211 if group
.delimiter() == delim
{
212 let end_of_group
= unsafe { self.ptr.add(*end_offset) }
;
213 let inside_of_group
= unsafe { Cursor::create(self.ptr.add(1), end_of_group) }
;
214 let after_group
= unsafe { Cursor::create(end_of_group, self.scope) }
;
215 return Some((inside_of_group
, group
.span(), after_group
));
222 /// If the cursor is pointing at a `Ident`, returns it along with a cursor
223 /// pointing at the next `TokenTree`.
224 pub fn ident(mut self) -> Option
<(Ident
, Cursor
<'a
>)> {
227 Entry
::Ident(ident
) => Some((ident
.clone(), unsafe { self.bump_ignore_group() }
)),
232 /// If the cursor is pointing at a `Punct`, returns it along with a cursor
233 /// pointing at the next `TokenTree`.
234 pub fn punct(mut self) -> Option
<(Punct
, Cursor
<'a
>)> {
237 Entry
::Punct(punct
) if punct
.as_char() != '
\''
=> {
238 Some((punct
.clone(), unsafe { self.bump_ignore_group() }
))
244 /// If the cursor is pointing at a `Literal`, return it along with a cursor
245 /// pointing at the next `TokenTree`.
246 pub fn literal(mut self) -> Option
<(Literal
, Cursor
<'a
>)> {
249 Entry
::Literal(literal
) => Some((literal
.clone(), unsafe { self.bump_ignore_group() }
)),
254 /// If the cursor is pointing at a `Lifetime`, returns it along with a
255 /// cursor pointing at the next `TokenTree`.
256 pub fn lifetime(mut self) -> Option
<(Lifetime
, Cursor
<'a
>)> {
259 Entry
::Punct(punct
) if punct
.as_char() == '
\''
&& punct
.spacing() == Spacing
::Joint
=> {
260 let next
= unsafe { self.bump_ignore_group() }
;
261 let (ident
, rest
) = next
.ident()?
;
262 let lifetime
= Lifetime
{
263 apostrophe
: punct
.span(),
266 Some((lifetime
, rest
))
272 /// Copies all remaining tokens visible from this cursor into a
274 pub fn token_stream(self) -> TokenStream
{
275 let mut tts
= Vec
::new();
276 let mut cursor
= self;
277 while let Some((tt
, rest
)) = cursor
.token_tree() {
281 tts
.into_iter().collect()
284 /// If the cursor is pointing at a `TokenTree`, returns it along with a
285 /// cursor pointing at the next `TokenTree`.
287 /// Returns `None` if the cursor has reached the end of its stream.
289 /// This method does not treat `None`-delimited groups as transparent, and
290 /// will return a `Group(None, ..)` if the cursor is looking at one.
291 pub fn token_tree(self) -> Option
<(TokenTree
, Cursor
<'a
>)> {
292 let (tree
, len
) = match self.entry() {
293 Entry
::Group(group
, end_offset
) => (group
.clone().into(), *end_offset
),
294 Entry
::Literal(literal
) => (literal
.clone().into(), 1),
295 Entry
::Ident(ident
) => (ident
.clone().into(), 1),
296 Entry
::Punct(punct
) => (punct
.clone().into(), 1),
297 Entry
::End(_
) => return None
,
300 let rest
= unsafe { Cursor::create(self.ptr.add(len), self.scope) }
;
304 /// Returns the `Span` of the current token, or `Span::call_site()` if this
305 /// cursor points to eof.
306 pub fn span(self) -> Span
{
308 Entry
::Group(group
, _
) => group
.span(),
309 Entry
::Literal(literal
) => literal
.span(),
310 Entry
::Ident(ident
) => ident
.span(),
311 Entry
::Punct(punct
) => punct
.span(),
312 Entry
::End(_
) => Span
::call_site(),
316 /// Skip over the next token without cloning it. Returns `None` if this
317 /// cursor points to eof.
319 /// This method treats `'lifetimes` as a single token.
320 pub(crate) fn skip(self) -> Option
<Cursor
<'a
>> {
321 let len
= match self.entry() {
322 Entry
::End(_
) => return None
,
324 // Treat lifetimes as a single tt for the purposes of 'skip'.
325 Entry
::Punct(punct
) if punct
.as_char() == '
\''
&& punct
.spacing() == Spacing
::Joint
=> {
326 match unsafe { &*self.ptr.add(1) }
{
327 Entry
::Ident(_
) => 2,
332 Entry
::Group(_
, end_offset
) => *end_offset
,
336 Some(unsafe { Cursor::create(self.ptr.add(len), self.scope) }
)
340 impl<'a
> Copy
for Cursor
<'a
> {}
342 impl<'a
> Clone
for Cursor
<'a
> {
343 fn clone(&self) -> Self {
348 impl<'a
> Eq
for Cursor
<'a
> {}
350 impl<'a
> PartialEq
for Cursor
<'a
> {
351 fn eq(&self, other
: &Self) -> bool
{
352 self.ptr
== other
.ptr
356 impl<'a
> PartialOrd
for Cursor
<'a
> {
357 fn partial_cmp(&self, other
: &Self) -> Option
<Ordering
> {
358 if same_buffer(*self, *other
) {
359 Some(self.ptr
.cmp(&other
.ptr
))
366 pub(crate) fn same_scope(a
: Cursor
, b
: Cursor
) -> bool
{
370 pub(crate) fn same_buffer(a
: Cursor
, b
: Cursor
) -> bool
{
372 match (&*a
.scope
, &*b
.scope
) {
373 (Entry
::End(a_offset
), Entry
::End(b_offset
)) => {
374 a
.scope
.offset(*a_offset
) == b
.scope
.offset(*b_offset
)
381 #[cfg(any(feature = "full", feature = "derive"))]
382 pub(crate) fn cmp_assuming_same_buffer(a
: Cursor
, b
: Cursor
) -> Ordering
{
386 pub(crate) fn open_span_of_group(cursor
: Cursor
) -> Span
{
387 match cursor
.entry() {
388 Entry
::Group(group
, _
) => group
.span_open(),
393 pub(crate) fn close_span_of_group(cursor
: Cursor
) -> Span
{
394 match cursor
.entry() {
395 Entry
::Group(group
, _
) => group
.span_close(),