crates/tt/src/buffer.rs

   1 //! Stateful iteration over token trees.
   2 //!
   3 //! We use this as the source of tokens for parser.
   4 use crate::{Leaf, Subtree, TokenTree};
   5
   6 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
   7 struct EntryId(usize);
   8
   9 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  10 struct EntryPtr(EntryId, usize);
  11
  12 /// Internal type which is used instead of `TokenTree` to represent a token tree
  13 /// within a `TokenBuffer`.
  14 #[derive(Debug)]
  15 enum Entry<'t> {
  16     // Mimicking types from proc-macro.
  17     Subtree(Option<&'t TokenTree>, &'t Subtree, EntryId),
  18     Leaf(&'t TokenTree),
  19     // End entries contain a pointer to the entry from the containing
  20     // token tree, or None if this is the outermost level.
  21     End(Option<EntryPtr>),
  22 }
  23
  24 /// A token tree buffer
  25 /// The safe version of `syn` [`TokenBuffer`](https://github.com/dtolnay/syn/blob/6533607f91686545cb034d2838beea338d9d0742/src/buffer.rs#L41)
  26 #[derive(Debug)]
  27 pub struct TokenBuffer<'t> {
  28     buffers: Vec<Box<[Entry<'t>]>>,
  29 }
  30
  31 trait TokenList<'a> {
  32     fn entries(&self) -> (Vec<(usize, (&'a Subtree, Option<&'a TokenTree>))>, Vec<Entry<'a>>);
  33 }
  34
  35 impl<'a> TokenList<'a> for &'a [TokenTree] {
  36     fn entries(&self) -> (Vec<(usize, (&'a Subtree, Option<&'a TokenTree>))>, Vec<Entry<'a>>) {
  37         // Must contain everything in tokens and then the Entry::End
  38         let start_capacity = self.len() + 1;
  39         let mut entries = Vec::with_capacity(start_capacity);
  40         let mut children = vec![];
  41         for (idx, tt) in self.iter().enumerate() {
  42             match tt {
  43                 TokenTree::Leaf(_) => {
  44                     entries.push(Entry::Leaf(tt));
  45                 }
  46                 TokenTree::Subtree(subtree) => {
  47                     entries.push(Entry::End(None));
  48                     children.push((idx, (subtree, Some(tt))));
  49                 }
  50             }
  51         }
  52         (children, entries)
  53     }
  54 }
  55
  56 impl<'a> TokenList<'a> for &'a Subtree {
  57     fn entries(&self) -> (Vec<(usize, (&'a Subtree, Option<&'a TokenTree>))>, Vec<Entry<'a>>) {
  58         // Must contain everything in tokens and then the Entry::End
  59         let mut entries = vec![];
  60         let mut children = vec![];
  61         entries.push(Entry::End(None));
  62         children.push((0usize, (*self, None)));
  63         (children, entries)
  64     }
  65 }
  66
  67 impl<'t> TokenBuffer<'t> {
  68     pub fn from_tokens(tokens: &'t [TokenTree]) -> TokenBuffer<'t> {
  69         Self::new(tokens)
  70     }
  71
  72     pub fn from_subtree(subtree: &'t Subtree) -> TokenBuffer<'t> {
  73         Self::new(subtree)
  74     }
  75
  76     fn new<T: TokenList<'t>>(tokens: T) -> TokenBuffer<'t> {
  77         let mut buffers = vec![];
  78         let idx = TokenBuffer::new_inner(tokens, &mut buffers, None);
  79         assert_eq!(idx, 0);
  80         TokenBuffer { buffers }
  81     }
  82
  83     fn new_inner<T: TokenList<'t>>(
  84         tokens: T,
  85         buffers: &mut Vec<Box<[Entry<'t>]>>,
  86         next: Option<EntryPtr>,
  87     ) -> usize {
  88         let (children, mut entries) = tokens.entries();
  89
  90         entries.push(Entry::End(next));
  91         let res = buffers.len();
  92         buffers.push(entries.into_boxed_slice());
  93
  94         for (child_idx, (subtree, tt)) in children {
  95             let idx = TokenBuffer::new_inner(
  96                 subtree.token_trees.as_slice(),
  97                 buffers,
  98                 Some(EntryPtr(EntryId(res), child_idx + 1)),
  99             );
 100             buffers[res].as_mut()[child_idx] = Entry::Subtree(tt, subtree, EntryId(idx));
 101         }
 102
 103         res
 104     }
 105
 106     /// Creates a cursor referencing the first token in the buffer and able to
 107     /// traverse until the end of the buffer.
 108     pub fn begin(&self) -> Cursor<'_> {
 109         Cursor::create(self, EntryPtr(EntryId(0), 0))
 110     }
 111
 112     fn entry(&self, ptr: &EntryPtr) -> Option<&Entry<'_>> {
 113         let id = ptr.0;
 114         self.buffers[id.0].get(ptr.1)
 115     }
 116 }
 117
 118 #[derive(Debug)]
 119 pub enum TokenTreeRef<'a> {
 120     Subtree(&'a Subtree, Option<&'a TokenTree>),
 121     Leaf(&'a Leaf, &'a TokenTree),
 122 }
 123
 124 impl<'a> TokenTreeRef<'a> {
 125     pub fn cloned(&self) -> TokenTree {
 126         match &self {
 127             TokenTreeRef::Subtree(subtree, tt) => match tt {
 128                 Some(it) => (*it).clone(),
 129                 None => (*subtree).clone().into(),
 130             },
 131             TokenTreeRef::Leaf(_, tt) => (*tt).clone(),
 132         }
 133     }
 134 }
 135
 136 /// A safe version of `Cursor` from `syn` crate <https://github.com/dtolnay/syn/blob/6533607f91686545cb034d2838beea338d9d0742/src/buffer.rs#L125>
 137 #[derive(Copy, Clone, Debug)]
 138 pub struct Cursor<'a> {
 139     buffer: &'a TokenBuffer<'a>,
 140     ptr: EntryPtr,
 141 }
 142
 143 impl<'a> PartialEq for Cursor<'a> {
 144     fn eq(&self, other: &Cursor<'_>) -> bool {
 145         self.ptr == other.ptr && std::ptr::eq(self.buffer, other.buffer)
 146     }
 147 }
 148
 149 impl<'a> Eq for Cursor<'a> {}
 150
 151 impl<'a> Cursor<'a> {
 152     /// Check whether it is eof
 153     pub fn eof(self) -> bool {
 154         matches!(self.buffer.entry(&self.ptr), None | Some(Entry::End(None)))
 155     }
 156
 157     /// If the cursor is pointing at the end of a subtree, returns
 158     /// the parent subtree
 159     pub fn end(self) -> Option<&'a Subtree> {
 160         match self.entry() {
 161             Some(Entry::End(Some(ptr))) => {
 162                 let idx = ptr.1;
 163                 if let Some(Entry::Subtree(_, subtree, _)) =
 164                     self.buffer.entry(&EntryPtr(ptr.0, idx - 1))
 165                 {
 166                     return Some(subtree);
 167                 }
 168                 None
 169             }
 170             _ => None,
 171         }
 172     }
 173
 174     fn entry(self) -> Option<&'a Entry<'a>> {
 175         self.buffer.entry(&self.ptr)
 176     }
 177
 178     /// If the cursor is pointing at a `Subtree`, returns
 179     /// a cursor into that subtree
 180     pub fn subtree(self) -> Option<Cursor<'a>> {
 181         match self.entry() {
 182             Some(Entry::Subtree(_, _, entry_id)) => {
 183                 Some(Cursor::create(self.buffer, EntryPtr(*entry_id, 0)))
 184             }
 185             _ => None,
 186         }
 187     }
 188
 189     /// If the cursor is pointing at a `TokenTree`, returns it
 190     pub fn token_tree(self) -> Option<TokenTreeRef<'a>> {
 191         match self.entry() {
 192             Some(Entry::Leaf(tt)) => match tt {
 193                 TokenTree::Leaf(leaf) => Some(TokenTreeRef::Leaf(leaf, *tt)),
 194                 TokenTree::Subtree(subtree) => Some(TokenTreeRef::Subtree(subtree, Some(tt))),
 195             },
 196             Some(Entry::Subtree(tt, subtree, _)) => Some(TokenTreeRef::Subtree(subtree, *tt)),
 197             Some(Entry::End(_)) | None => None,
 198         }
 199     }
 200
 201     fn create(buffer: &'a TokenBuffer<'_>, ptr: EntryPtr) -> Cursor<'a> {
 202         Cursor { buffer, ptr }
 203     }
 204
 205     /// Bump the cursor
 206     pub fn bump(self) -> Cursor<'a> {
 207         if let Some(Entry::End(exit)) = self.buffer.entry(&self.ptr) {
 208             match exit {
 209                 Some(exit) => Cursor::create(self.buffer, *exit),
 210                 None => self,
 211             }
 212         } else {
 213             Cursor::create(self.buffer, EntryPtr(self.ptr.0, self.ptr.1 + 1))
 214         }
 215     }
 216
 217     /// Bump the cursor, if it is a subtree, returns
 218     /// a cursor into that subtree
 219     pub fn bump_subtree(self) -> Cursor<'a> {
 220         match self.entry() {
 221             Some(Entry::Subtree(_, _, _)) => self.subtree().unwrap(),
 222             _ => self.bump(),
 223         }
 224     }
 225
 226     /// Check whether it is a top level
 227     pub fn is_root(&self) -> bool {
 228         let entry_id = self.ptr.0;
 229         entry_id.0 == 0
 230     }
 231 }