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